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.DS2025
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…
cs.DC2024
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…