4 papers
Complexity landscape for local certification
Nicolas Bousquet, Laurent Feuilloley, Sébastien Zeitoun
An impressive recent line of work has charted the complexity landscape of distributed graph algorithms. For many settings, it has been determined which time complexities exist, and…
Reductions in local certification
Louis Esperet, Sébastien Zeitoun
Local certification is a topic originating from distributed computing, where a prover tries to convince the vertices of a graph that satisfies some property .…
A subquadratic certification scheme for P5-free graphs
Nicolas Bousquet, Sébastien Zeitoun
In local certification, vertices of a -vertex graph perform a local verification to check if a given property is satisfied by the graph. This verification is performed thanks to…
Renaming in distributed certification
Nicolas Bousquet, Louis Esperet, Laurent Feuilloley +1
Local certification is the area of distributed network computing asking the following question: How to certify to the nodes of a network that a global property holds, if they are l…