Strong and Hiding Distributed Certification of Bipartiteness

Benjamin Jauregui, Augusto Modanese, Pedro Montealegre, Martín Ríos-Wilson · 2025

Read Strong and Hiding Distributed Certification of Bipartiteness by Benjamin Jauregui, Augusto Modanese, Pedro Montealegre, Martín Ríos-Wilson (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-13854.txt.

Description

Benjamin Jauregui, Augusto Modanese, Pedro Montealegre, and Martin Rios-Wilson study local proofs for graph coloring in a 2025 paper. A graph is bipartite when its nodes split into two camps with no edge inside a camp, which matches a two-coloring. In a locally checkable proof, each node holds a small certificate that neighbors can verify. The twist here: the proof should hide the coloring itself, yet be strongly sound.

Strong soundness means that in any non-bipartite graph, the nodes that accept must still form a bipartite piece. The authors show such hiding, strong proofs exist for some graph classes with small certificates. For cycles or graphs with a leaf node, even constant-size certificates work in anonymous networks. For general graphs, though, they prove hiding strong proofs need growing certificates and node identities.

Catalog record

CREATORBenjamin Jauregui, Augusto Modanese, Pedro Montealegre, Martín Ríos-Wilson
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE160 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-13854

Browse the full library · About the Tower of Babel