MC2

Our main objective is to understand the power and limitations of efficient algorithms, considering various models of computation: sequential model, algebraic complexity, symbolic dynamics, quantum computing, molecular programming. The main mathematical tools of our research are combinatorics and algebra.

• 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.
  
  
• 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.
  
  
• Quantum information
  Quantum devices have a great potential for information technology. One of the main bottlenecks in building quantum computers is the presence of noise. Our research aims at designing ways to perform computation and communication efficiently using noisy devices. This includes designing error-correcting codes and fault-tolerant schemes.
  
  
• Symbolic dynamics
  One of our goals is to explore computational and combinatorial aspects of symbolic dynamics on finitely generated groups. We aim to tackle three difficult questions: first, characterizing finitely generated groups with decidable Domino problem; second, understanding which groups admit aperiodic SFTs ; third, defining powerful tools to compute the entropy of 2D subshifts.