Calendrier des animations scientifiques

It is well-known that there exist planar graphs which cannot be vertex-partitionned into 2 forests. However, it is a long standing conjecture whether Eulerian planar triangulations admit such a vertex-partition (Barnette 1969). The oriented restrictions are also open: does every Eulerian oriented planar triangulation admit a vertex-partition into 2 directed acyclic graphs (Barnette x Neumann-Lara) ? A CAI-partition (A,I) of a (oriented) graph is a vertex-partition in two parts A and I, where A induces a connected acyclic (oriented) graph and I is an independent set. An angle to attack the above mentionned conjectures, is to use 3-colorability of Eulerian triangulations, and try to build a CAI-partition for the subgraph induced by two out of three color classes. We show that this is not always possible. On the positive side, we show that bipartite 2-vertex-connected subcubic oriented graphs admit a CAI-partition, and (almost) none of the restrictions can be dropped.

Joint work with Stijn Cambie, François Dross, Kolja Knauer and Hoang La.

L’optimisation du transport public repose sur plusieurs étapes clés. Tout d’abord, il est nécessaire d’estimer les matrices origine-destination, afin de comprendre comment les usagers se déplacent dans le réseau de transport public. Ensuite, il faut définir les fréquences de passage, les horaires de départ des trajets, ainsi que l’affectation des véhicules et des conducteurs. Enfin, un contrôle en temps réel est indispensable pour gérer les imprévus et assurer la robustesse du système. Dans cette présentation, je montrerai les méthodologies que j’ai utilisées pour résoudre ces problèmes, ainsi que les défis scientifiques qui restent à modéliser.

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.