4 papers · 1 filter
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…
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…
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…