Our main objective is to understand the power and limitations of efficient algorithms, considering various models of computation: sequential model, algebraic complexity, symbolic dynamics, 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.
  
  
• Biomolecular computation models
  Our goal is to design biomolecules with computation capacities. Our approach is two-fold: theoretical by developing and studying models for evaluating the computational capacities of molecular systems, and experimental by designing and realizing in wet lab molecular systems implementing algorithms at the nanoscopic molecular scale.
  
  
• 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.
  
  
• 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.