5 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…
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…
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…
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…