32 citations · 76 across the 27 of their papers we have counts for
34 papers
The local complexity of certifying parity
Nicolas Bousquet, Laurent Feuilloley, Jorge Valenzuela +1
In this paper, we consider the problem of locally certifying that the size of a network is even, or more generally, congruent to some fixed number. The parity property is one of th…
Polynomial Time Local Decision Revisited
Laurent Feuilloley, Soumyadeep Paul, Ami Paz
We consider three classification systems for distributed decision tasks: With unbounded computation and certificates, defined by Balliu, D'Angelo, Fraigniaud, and Olivetti [JCSS'18…
Decreasing verification radius in local certification
Laurent Feuilloley, Jan Janoušek, Jan Matyáš Křišťan +1
This paper deals with local certification, specifically locally checkable proofs: given a graph property, the task is to certify whether a graph satisfies the property. The verific…
Global certification via perfect hashing
Nicolas Bousquet, Laurent Feuilloley, Sébastien Zeitoun
In this work, we provide an upper bound for global certification of graph homomorphism, a generalization of graph coloring. In certification, the nodes of a network should decide i…
Local certification of forbidden subgraphs
Nicolas Bousquet, Linda Cook, Laurent Feuilloley +2
Detecting specific structures in a network has been a very active theme of research in distributed computing for at least a decade. In this paper, we start the study of subgraph de…
Local certification of local properties: tight bounds, trade-offs and new parameters
Nicolas Bousquet, Laurent Feuilloley, Sébastien Zeitoun
Local certification is a distributed mechanism enabling the nodes of a network to check the correctness of the current configuration, thanks to small pieces of information called c…