4 papers
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, Tytus Grodzicki, Tomasz JurdziÅski +2
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 and Fast Algorithms for k-gathering and k-broadcasting
Adam Ganczorz, Tomasz Jurdzinski
We consider basic communication tasks in arbitrary radio networks: -broadcasting and -gathering. In the case of -broadcasting messages from sources have to get to all…