Anonymous parity certification requires logarithmic size certificates for sparse graphs
Tight Bounds for Anonymous Parity Certification
Distributed, Parallel, and Cluster Computing
Summary
Checking if a network graph has an even or odd number of nodes can be tricky when nodes have no unique IDs and can only see their immediate neighbors. The authors show the smallest amount of information (certificate size) each node needs to verify the network’s parity depends on how sparse or connected the graph is. They find exact bounds for general graphs and explore how different notions of sparsity affect this verification complexity. This helps understand the limits of local checking in networks without unique identifiers.
What this means in practice
- •For network protocol designers: Determine minimal certificate size needed to verify global network properties in anonymous distributed systems based on network sparsity.
- •For distributed system engineers: Guide the design of local verification algorithms for networks without unique identifiers, tuning certificate sizes for different sparsity classes.
A theory result. No direct application yet.
Authors
Pedro Montealegre, Jorge Valenzuela
Abstract
Local certification is the task of verifying graph properties using certificates assigned to vertices and checked using only local information. A central question is which properties admit constant-size certificates, independently of network size. A fundamental test case is the parity of the network order. Bousquet, Feuilloley, Valenzuela, and Zeitoun (DISC 2026) showed that the complexity of certifying even order depends dramatically on the verification model. On arbitrary graphs, three bits per vertex suffice with unique identifiers and verification radius two. In the anonymous radius-one model, they established an $Ω(\log\log^* n)$ lower bound and an $O(\log n)$ upper bound. They also showed that constant-size certificates suffice in this model on bounded-expansion classes. In this paper, we settle the complexity of anonymous parity certification on general graphs and further investigate the role of graph sparsity. Our main contributions are: * We close the gap left by Bousquet et al., proving that the local complexity of certifying even order in the anonymous radius-one model is $Θ(\log\log n)$ bits. * We show that on graphs of degeneracy at most $d$, parity can be certified with $O(\log d)$ bits, while $Ω(\log\log d)$ bits are necessary. In particular, every class of bounded degeneracy admits constant-size certificates, strictly generalizing the result for bounded-expansion classes. * We show that constant-size certification cannot be guaranteed on nowhere-dense classes, a broader notion of sparsity that includes bounded expansion. We construct a fixed, subgraph-closed nowhere-dense class on which parity certification requires $Θ(\log\log n)$ bits. Together, our results provide a more complete picture of anonymous parity certification on sparse graph classes, showing that its complexity depends on the particular structural notion of sparsity.