We study the limits of efficient computation across algorithms, logic, and graph structure:

How far can algorithms be optimized? How expressive can a logic be while retaining tractability?

Download project PDF

People

LIP

Lyon

LAMSADE

Paris

IRIF

Paris

Meetings

To be announced.

Publications

  1. Édouard Bonnet, Yeonsu Chang

    Max Independent Set Remains NP-hard when Excluding a Planar Induced Minor

    CoRR abs/2609.11285 (2026)

  2. Édouard Bonnet, Julien Duron, Marcin Pilipczuk, Marek Sokołowski, Szymon Toruńczyk

    Time-Optimal APSP and Matrix Multiplication in Classes of Linear Neighborhood Complexity

    CoRR abs/2608.25212 (2026)

  3. Édouard Bonnet, Maël Dumas, Julien Duron

    Independent Set Hardness in Graphs of Bounded Twin-Width and Low-Radius Merge-Width

    IPEC 2026

  4. Ignasi Sau, Nicole Schirrmacher, Sebastian Siebertz, Giannos Stamoulis, Dimitrios M. Thilikos, Alexandre Vigny

    Model Checking for Low Monodimensionality Fragments of CMSO on Topological-Minor-Free Graph Classes

    LICS 2026

  5. Michael Lampis

    k-SUM Hardness Implies Treewidth-SETH

    SODA 2026: 1916–1944