Calendrier des animations scientifiques

We introduce structured‑seed local pseudorandom generators (SSL-PRGs), pseudorandom generators whose seed is drawn from an efficiently sampleable, structured distribution rather than uniformly. This seemingly modest relaxation turns out to capture many known applications of local PRGs, yet it can be realized from a broader family of hardness assumptions. Our main technical contribution is a generic template for constructing SSL-PRGs that combines the following two ingredients:
(i) noisy‑NC0 PRGs, computable by constant‑depth circuits fed with sparse noise, with
(ii) new local compression schemes for sparse vectors derived from combinatorial batch codes.

Instantiating the template under the sparse Learning‑Parity‑with‑Noise (LPN) assumption yields the first SSL-PRGs with polynomial stretch and constant locality from a subquadratic‑sample search hardness assumption; a mild strengthening of sparse‑LPN gives strong SSL-PRGs of arbitrary polynomial stretch. We further show that for all standard noise distributions, noisy‑local PRGs cannot be emulated by ordinary local PRGs, thereby separating the two notions.

Plugging SSL-PRGs into existing frameworks, we revisit the canonical applications of local PRGs and demonstrate that SSL-PRGs suffice for:
(i) indistinguishability obfuscation,
(ii) constant-overhead secure computation,
(iii) compact homomorphic secret sharing, and
(iv) deriving hardness results for PAC‑learning DNFs from sparse‑LPN.

Our work thus broadens the landscape of low‑depth pseudorandomness and anchors several primitives to a common, well‑motivated assumption.

Joint work with Benny Applebaum, Dung Bui, and Geoffroy Couteau.

Un graphe de cercle est le graphe d’intersection de cordes inscrites dans un
cercle. En 2014, avec D. Corneil, E. Gioan et M. Tedder, nous avons publié un
algorithme quasi-linéaire pour la reconnaissance des graphes de cercle. Comme
ses prédécesseurs, cet algorithme repose sur le calcul de la décomposition en coupes.
En utilisant un ordre LexBFS, nous avions montré comment la décomposition en coupes
pouvait être calculer en temps quasi-linéaire. L’obstacle à une complexité linéaire était
l’utilisation de l’union-find pour mettre à jour l’arbre de décomposition lors de l’insertion
d’un sommet. Même dans le cas restreint des graphes de cercle, nous n’avions pas
réussi à lever cet obstacle. L’existence d’un algorithme linéaire pour la reconnaissance
des graphes de cercle restait une question ouverte. Avec I. Rutter (Univ. Passau), nous
montrons que c’est possible en utilisant des arbres-PC.

In recent years, there has been a rising demand for transparent and explainable AI models. Although significant progress has been made in providing explanations for machine learning (ML) models, this topic has not received the same attention in the Operations Research (OR) community. However, algorithmic decisions in OR are made by complex algorithms which cannot be considered to be explainable or transparent as we will argue in this talk. To tackle this issue we present two promising concepts to provide explanations for (integer) optimization problems. In the first part we introduce the concept of counterfactual explanations and show how it can be used to calculate explanations for linear integer optimization problems. We show that the resulting problem is Sigma_2^p-hard but can be solved in reasonable time for certain special cases. In the second part we present a model-agnostic method called CLEMO which can provide explanations for any type of optimization algorithms (exact or heuristic). The idea is to approximate the input-output relationship of an optimization algorithm by an interpretable ML model.

For a finite collection of connected graphs F, the F-Minor Deletion problem consists in, given a graph G and an integer l, deciding whether G contains a vertex set of size at most l whose removal results in an F-minor-free graph. We lift the existence of approximate polynomial kernels for F-Minor Deletion by the solution size to approximate polynomial kernels parameterized by the vertex-deletion distance to graphs of bounded elimination distance to F-minor-free graphs. This results in exact polynomial kernels for every family F that contains a planar graph, and an approximate polynomial kernel for Planar Vertex Deletion. Moreover, combining our result with a previous lower bound, we obtain the following infinite set of dichotomies, assuming NP is not contained in coNP/poly: for any finite set F of biconnected graphs on at least three vertices containing a planar graph, and any minor-closed class of graphs C, F-Minor Deletion admits a polynomial kernel parameterized by the vertex-deletion distance to C if and only if C has bounded elimination distance to F-minor-free graphs. For instance, this yields dichotomies for Cactus Vertex Deletion, Outerplanar Vertex Deletion, and Treewidth-t Vertex Deletion for every integer t ≥ 0. Prior to our work, such dichotomies were only known for the particular cases of Vertex Cover and Feedback Vertex Set. Our approach builds on the techniques developed by Jansen and Pieterse [Theor. Comput. Sci. 2020] and also uses adaptations of some of the results by Jansen, de Kroon, and Wlodarczyk [STOC 2021].

Joint work with Marin Bougeret and Ignasi Sau.

The capacitated vehicle routing problem with time windows (CVRPTW) is often faced by Postal services in the context of package delivery or other time-sensitive operations. We provide an implementation on gate based quantum computer of a model inspired by classical route first, cluster second technique. The quantum paradigm allows to overcome suboptimality inherent property of this decomposition. In the current NISQ (Noisy Intermediate-Scale Quantum) era, the most important limitation is the number of available qubits which makes time windows and capacity constraints hard to tackle. We introduce a qubit-efficient split-inspired modeling which adds only a linear number of decision qubits to standard quantum formulations for Traveling Salesman Problem (TSP). This paper proposes a quantum algorithm for the capacitated vehicle routing problem with time windows (CVRPTW) based on Grover Search framework. This problem is often faced by Postal services in the context of package delivery or other time-sensitive operations. We provide an implementation on gate based quantum computer of a model inspired by classical route first, cluster second technique. The quantum paradigm allows to overcome suboptimality inherent property of this decomposition. In the current NISQ (Noisy Intermediate-Scale Quantum) era, the most important limitation is the number of available qubits which makes time windows and capacity constraints hard to tackle. We introduce a qubit-efficient split-inspired modeling which adds only a linear number of decision qubits to standard quantum formulations for Traveling Salesman Problem (TSP).

Decision-Dependent Information Discovery (DDID), a variant of two-stage robust optimization, addresses problems where uncertainty can be reduced by querying the values of some uncertain parameters before making decisions for the nominal problem. In this work, we study DDID applied to combinatorial problems under a robust capacity constraint. In our setting, the number of uncertain parameters that can be queried in the first stage is limited by a given integer q. We show that if q is considered as a constant, then some classical nominal combinatorial problems—such as selection problem, spanning tree problem and assignment problem—remain polynomial-time solvable in this robust optimization setting. Specifically, we prove that their objective functions can be computed by solving polynomial number of (compact) linear programs.

TBA