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
| CREATOR | Benjamin Jauregui, Augusto Modanese, Pedro Montealegre, Martín Ríos-Wilson |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 160 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-13854