3 papers
cs.DC2026
Short Graph Sketches Suffice for Error-resilient Leader Verification in CONGEST
Pawel Garncarek, Tomasz JurdziÅski, Dariusz Kowalski +1
Locally Checkable Proofs (LCPs) enable the verification of global graph properties using locally checkable certificates assigned by a prover. Recently, this framework was extended…
cs.DC2026
Distributed Local Verification using Proofs with(out) Errors
PaweÅ Garncarek, Tomasz Jurdzinski, Dariusz Kowalski +1
We study local verification of graph properties in distributed networks under the framework of \emph{locally checkable proofs} (LCPs). In an LCP, a prover assigns proof labels to n…
cs.DC2025
Beeping Deterministic CONGEST Algorithms in Graphs
Pawel Garncarek, Dariusz R. Kowalski, Shay Kutten +1
The Beeping Network (BN) model captures important properties of biological processes. Paradoxically, the extremely limited communication capabilities of such nodes has helped BN be…