Search Results

Documents authored by Valenzuela, Jorge


Document
The Local Complexity of Certifying Parity

Authors: Nicolas Bousquet, Laurent Feuilloley, Jorge Valenzuela, and Sébastien Zeitoun

Published in: LIPIcs, Volume 397, 40th International Symposium on Distributed Computing (DISC 2026)


Abstract
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 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 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.

Cite as

Nicolas Bousquet, Laurent Feuilloley, Jorge Valenzuela, and Sébastien Zeitoun. The Local Complexity of Certifying Parity. In 40th International Symposium on Distributed Computing (DISC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 397, pp. 22:1-22:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)


Copy BibTex To Clipboard

@InProceedings{bousquet_et_al:LIPIcs.DISC.2026.22,
  author =	{Bousquet, Nicolas and Feuilloley, Laurent and Valenzuela, Jorge and Zeitoun, S\'{e}bastien},
  title =	{{The Local Complexity of Certifying Parity}},
  booktitle =	{40th International Symposium on Distributed Computing (DISC 2026)},
  pages =	{22:1--22:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-454-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{397},
  editor =	{Moses Jr., William K. and Censor-Hillel, Keren},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2026.22},
  URN =		{urn:nbn:de:0030-drops-281285},
  doi =		{10.4230/LIPIcs.DISC.2026.22},
  annote =	{Keywords: Local certification, proof-labeling schemes, locally checkable proofs, space complexity, parity, congruence, lower bound}
}

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail