Laurent Feuilloley

Nicolas Bousquet, Laurent Feuilloley, Jorge Valenzuela et al.

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 the simplest global properties, and it plays an intriguing role in local certification. On the one hand, it is one of the simplest properties in cycles because it is equivalent to 2-colorability, and hence can be certified with a single bit. On the other hand, in general graphs, no non-trivial lower bound on the size of the certificates is known, and the known upper bound basically consists in certifying the \emph{exact} value of $n$. In addition, the nature of the problem makes all the known lower bound approaches fail. We uncover a surprising landscape for parity across different models and graph structures: * In general graphs equipped with identifiers, when allowing verification radius 2, parity can be certified with a constant number of bits. * But in the model of anonymous graphs and allowing verification radius only 1, parity requires $Ω(\log \log^*n)$ bits. * Finally, in bounded expansion graph classes (such as bounded-degree graphs and planar graphs), the lower bound does not apply: in the same restricted model we can design a constant-size certification. We introduce several new tools that we expect to be useful in other contexts, in particular ways to \emph{encode a parent at each node with a constant number of bits} (via implicit use of the IDs and conflict-free colorings) and a new lower bound technique, with complex topologies and higher-order Ramsey-type arguments.

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], and with (two flavors of) polynomially bounded local computation and certificates, defined in recent works by Aldema Tshuva and Oshman [OPODIS'23], and by Reiter [PODC'24]. The latter two differ in the way they evaluate the polynomial bounds: the former considers polynomials with respect to the size of the graph, while the latter refers to being polynomial in the size of each node's local neighborhood. We start by revisiting decision without certificates. For this scenario, we show that the latter two definitions coincide: roughly, a node cannot know the graph size, and thus can only use a running time dependent on its neighborhood. We then consider decision with certificates. With existential certificates ($Σ_1$-type classes), a larger running time defines strictly larger classes of languages: when it grows from being polynomial in each node's view, through polynomial in the graph's size, and to unbounded, the derived classes strictly contain each other. With universal certificates ($Π_1$-type classes), on the other hand, we prove a surprising incomparability result: having running time bounded by the graph size sometimes allows us to decide languages undecidable even with unbounded certificates. We complement these results with other containment and separation results, which together portray a surprisingly complex lattice of strict containment relations between the classes at the base of the three classification systems.