Parity of network size can be locally certified with constant bits using IDs at radius 2 or in bounded-expansion graphs at radius 1, but needs Ω(log log* n) bits in anonymous radius-1 model.
6Jérémie Chalopin, Victor Chepoi, and Maria Kokkou
2 Pith papers cite this work. Polarity classification is still indexing.
2
Pith papers citing it
years
2026 2verdicts
UNVERDICTED 2representative citing papers
A 1-PLS of cost p implies a t-PLS of cost O(ceil(p/t)) up to log n factors in general graphs and O(ceil(p/t) + log n) in fixed minor-free graphs.
citing papers explorer
-
The local complexity of certifying parity
Parity of network size can be locally certified with constant bits using IDs at radius 2 or in bounded-expansion graphs at radius 1, but needs Ω(log log* n) bits in anonymous radius-1 model.
-
Near-Resolution of the Tradeoff Conjecture in Distributed Proof Labeling Schemes
A 1-PLS of cost p implies a t-PLS of cost O(ceil(p/t)) up to log n factors in general graphs and O(ceil(p/t) + log n) in fixed minor-free graphs.