Laurent Feuilloley: Publications by year

→ Every paper has its own small webpage (with slides, links etc.). Just click on the title!

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

Local certification of forbidden subgraphs
with Nicolas Bousquet, Linda Cook, Théo Pierron, and Sébastien Zeitoun. arxiv version.
Global certification via perfect hashing
with Nicolas Bousquet and Sébastien Zeitoun. arxiv version
Pattern detection in ordered graphs
with Guillaume Ducoffe, Michel Habib and François Pitois. arxiv version
Short and local transformations between (Δ+1)-colorings
with Nicolas Bousquet, Marc Heinrich and Mikaël Rabie. arxiv version
Classifying grounded intersection graphs via ordered forbidden patterns
with Michel Habib. arxiv version.

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)

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).

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.

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.

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.

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).