Laurent Feuilloley: Publications by year

→ Every paper has its own small webpage (with slides, links etc.). Just click on the title! Note that there are duplicates (journal and conference version of the same paper).

For informal publications (and publications in French) see also my other works and the blog.

Preprints

Local certification of forbidden subgraphs
with Nicolas Bousquet, Linda Cook, Théo Pierron, and Sébastien Zeitoun. arxiv version.
Pattern detection in ordered graphs
with Guillaume Ducoffe, Michel Habib and François Pitois. arxiv version
Classifying grounded intersection graphs via ordered forbidden patterns
with Michel Habib. arxiv version.

To appear

Proving there is a leader without naming it
with Josef Erik Sedláček and Martin Slávik. SIROCCO 2026 arxiv version.
Polynomial Time Local Decision Revisited
with Soumyadeep Paul and Ami Paz. SIROCCO 2026.

2026

Renaming in distributed certification
with Nicolas Bousquet, Louis Esperet and Sébastien Zeitoun.Theoretical Computer Science (TCS) 2026

2025

Complexity landscape for local certification
with Nicolas Bousquet and Sébastien Zeitoun. DISC 2025 (Best Paper Award).
Local certification of local properties: tight bounds, trade-offs and new parameters
with Nicolas Bousquet and Sébastien Zeitoun. SIAM Journal of Discrete Mathematics (SIDMA).
Decreasing verification radius in local certification
with Josef Erik Sedláček, Jan Matyáš Křišťan and Jan Janoušek. Theoretical Computer Science (TCS)
When Should You Wait Before Updating? Toward a Robustness Refinement
with Swan Dubois, Franck Petit et Mikaël Rabie. Theoretical Computer Science (TCS)
Short and local transformations between (Δ+1)-colorings
with Nicolas Bousquet, Marc Heinrich and Mikaël Rabie. Innovations in Graph Theory

2024

How local constraints influence network diameter and applications to LCL generalizations
with Nicolas Bousquet and Théo Pierron. OPODIS 2024
The Secretary Problem with Independent Sampling
with José Correa, Andrés Cristi, Tim Oosterwijk and Alexandros Tsigonias-Dimitriadis. Management Science
Local certification of graph decompositions and applications to minor-free classes
with Nicolas Bousquet and Théo Pierron. Journal of parallel and distributed Computing. (JPDC)
Decreasing verification radius in local certification
with Josef Erik Sedláček, Jan Matyáš Křišťan and Jan Janoušek. ALGOWIN 2024
Brief Announcement: Global certification via perfect hashing
with Nicolas Bousquet and Sébastien Zeitoun. PODC 2024
Local certification of local properties: tight bounds, trade-offs and new parameters
with Nicolas Bousquet and Sébastien Zeitoun. STACS 2024.

2023

Lower bound for constant-size local certification
with Virgina Ardévol Martínez, Marco Caoduro, Jonathan Narboni, Pegah Pournajafi, and Jean-Florent Raymond. TCS.
When Should You Wait Before Updating? Toward a Robustness Refinement
with Swan Dubois, Franck Petit et Mikaël Rabie. SAND 2023.
Optimal Space Lower Bound for Deterministic Self-Stabilizing Leader Election Algorithms
with Lélia Blin and Gabriel Le Bouder. Discrete Mathematics and Theoretical Computer Science (DMTCS)
Local Certification of Graphs with Bounded Genus
with Pierre Fraigniaud, Ivan Rapaport, Éric Rémila, Pedro Montealegre and Ioan Todinca. Discrete Applied Mathematics (DAM)

2022

Lower bound for constant-size local certification
with Virgina Ardévol Martínez, Marco Caoduro, Jonathan Narboni, Pegah Pournajafi, and Jean-Florent Raymond. SSS 2022.
What can be certified compactly?
with Nicolas Bousquet and Théo Pierron. PODC 2022.
Error-Sensitive Proof-Labeling Schemes
with Pierre Fraigniaud. Journal of Parallel and Distributed Computing (JPDC).

2021

Distributed recoloring of interval and chordal graphs
with Nicolas Bousquet, Marc Heinrich and Mikael Rabie. OPODIS 2021.
Local certification of graph decompositions and applications to minor-free classes
with Nicolas Bousquet and Théo Pierron. OPODIS 2021.
Optimal Space Lower Bound for Deterministic Self-Stabilizing Leader Election Algorithms
with Lélia Blin and Gabriel Le Bouder. OPODIS 2021.
Randomized local network computing: Derandomization Beyond Locally Checkable Labelings
with Pierre Fraigniaud. ACM Transactions on Parallel Computing.
Brief announcement: Local certification of graph decompositions and applications to minor-free classes
with Nicolas Bousquet and Théo Pierron. DISC 2021.
Introduction to local certification
Discrete Mathematics and Theoretical Computer Science (DMTCS).
Compact Distributed Certification of Planar Graphs
with Pierre Fraigniaud, Ivan Rapaport, Éric Rémila, Pedro Montealegre and Ioan Todinca. Algorithmica.
A Hierarchy of Local Decision
with Pierre Fraigniaud and Juho Hirvonen. Theoretical Computer Science (TCS).
The Secretary Problem with Independent Sampling
with José Correa, Andrés Cristi, Tim Oosterwijk and Alexandros Tsigonias-Dimitriadis. SODA 2021
Graph classes and forbidden patterns on three vertices
with Michel Habib. SIAM Journal on Discrete Mathematics (SIDMA).
Redundancy in Distributed Proofs
with Pierre Fraigniaud, Juho Hirvonen, Ami Paz and Mor Perry. Distributed computing.

2020

Silent MST approximation for tiny memory
with Lélia Blin and Swan Dubois. SSS 2020
Compact Distributed Certification of Planar Graphs
with Pierre Fraigniaud, Ivan Rapaport, Éric Rémila, Pedro Montealegre and Ioan Todinca. PODC 2020.
How long it takes for an ordinary node with an ordinary ID to output?
Theoretical Computer Science.

2016

Survey of Distributed Decision.
with Pierre Fraigniaud. Bulletin of the EATCS, No 119.
A Hierarchy of Local Decision.
with Pierre Fraigniaud and Juho Hirvonen. ICALP 2016.

2015

Locally Optimal Load Balancing.
with Juho Hirvonen and Jukka Suomela. DISC 2015.
Brief Announcement: Average Complexity for the LOCAL Model.
PODC 2015.
Randomized Local Network Computing.
with Pierre Fraigniaud. SPAA 2015.
Independent and Hitting Sets of Rectangles Intersecting a Diagonal Line: Algorithms and Complexity.
with José R. Correa, Pablo Pérez-Lantero and José A. Soto. Discrete & Computational Geometry, Volume 53 (2015).

2014

Independent and Hitting Sets of Rectangles Intersecting a Diagonal Line.
with José R. Correa et José A. Soto. LATIN 2014.