Published in: LIPIcs, Volume 397, 40th International Symposium on Distributed Computing (DISC 2026)
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)
@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}
}