In our research we aim to understand the power and limitations of efficient algorithms. To this end, we design and analyse algorithms, and set impossibility results (completeness results or, when possible, unconditional lower bounds). We also study the relevant combinatorial structures.
Various models of computation can be considered to allow different features in the algorithms (eg, sequential vs parallel, synchronous vs asynchronous, deterministic vs probabilistic). Various complexity measures can be considered to quantify efficiency, such as time, space, communications.
Among the several fields of mathematics at the heart of this research, our team focuses on algebra and combinatorics. Both of these areas are a source of algorithmic problems which play key roles in the architecture of complexity theory (eg, the complexity of computing matrix permanents or graph colourings). Both areas also provide mathematical tools which are essential to proving theorems in complexity theory (eg, advanced linear algebra and graph theory for de-randomization or the study of approximation and parameterized algorithms).
- Team leader: Stephan THOMASSÉ
- Staff: Laure SAVETIER
Keywords
Graph theory and graph algorithms, combinatorics, biomolecular computing models, discrete and algebraic algorithms, disc and sphere packings, complexity theory.
Research topics
Graph theory and algorithms
Our research deals with structural properties of graphs, which can then be used in order to design new algorithmic tools (e.g.: polynomial exact or approximation algorithms, parameterized or moderately exponential algorithms). Among other graph problems, we focus on the chromatic number, the independence number, or the maximum clique number of a graph.
Contacts: Édouard BONNET, Carl FEGHALI, Jean-Florent RAYMOND, Éric THIERRY, Stephan THOMASSÉ, Nicolas TROTIGNON, Rémi WATRIGANT
Interactions between graphs and logic
We study different logics for talking about properties on graphs. We investigate several reasoning tasks like model checking (does a given graph satisfy a given property?) and satisfiability problem (is there a graph satisfying a given property?).
We focus on modal logic for reasoning about knowledge in multi-agent systems (e.g. does agent A know that agent B does not know that the area is safe?), where graphs are Kripke structures.
We also design logics for reasoning about graph neural networks (GNNs), in order to verify the behavior of GNNs (e.g. does some trained GNN classify as toxic any molecule satisfying a given property?).
Contacts: Édouard BONNET, François SCHWARZENTRUBER, Stephan THOMASSÉ
Algebraic complexity
We study an algebraic analogue of the P versus NP problem based on the computation model of arithmetic circuits. These circuits are made of addition and multiplication gates (instead of boolean gates in boolean circuits) and therefore compute polynomials. We also work on arithmetic circuit reconstruction and in particular on tensor decomposition. This task can be viewed as an algebraic analogue of computational learning.
Contacts: Pascal KOIRAN, Natacha PORTIER
Combinatorics, discrete structures & symbolic dynamics
We are looking in the archives for old open problems that no one can solve but us.
Contact: Daria PCHELINA, Michaël RAO
Biomolecular computation models: theory and experiments
Our goal is to design biomolecules with computation capacities. Our approach is two-fold:
- Theory: We are developing and studying models for evaluating the computational capacities of molecular systems. For instance, we have recently introduced the Turedo model that allowed us to prove that co-transcriptional molecular folding model modeled as Oritatami is able to produce uncomputable configurations.
- Wetlab experiments: We are designing and realizing in wet lab, molecular systems implementing algorithms at the nanoscopic molecular scale. These systems are inspired by the models developped above.
Contact: Daria PCHELINA, Nicolas SCHABANEL