3 papers
cs.DC2026
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…
cs.DC2026
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…
cs.DC2024
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…