4 papers · 1 filter
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…
Efficient Stable Population Protocols for Parity and Beyond
Leszek Gąsieniec, Leszek GÄ sieniec, Tytus Grodzicki +4
For nearly two decades, population protocols have been extensively studied, yielding efficient solutions for central problems in distributed computing, including leader election, a…
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…
Optimal-Length Labeling Schemes for Fast Deterministic Communication in Radio Networks
Adam GaÅczorz, Tomasz JurdziÅski, Andrzej Pelc
We consider two fundamental communication tasks in arbitrary radio networks: broadcasting (information from one source has to reach all nodes) and gossiping (every node has a messa…