Preprint
Sep 2026
Distributed Lower Bounds via Automatic Self-Reduction
The development of round elimination into a general-purpose technique [PODC 2019] marked a turning point in our understanding of the hardness of many graph problems in the distributed setting and led to several breakthrough results. However, the round elimination technique seems unable to yield randomized lower bounds...
A. Balliu, Francesco d'Amore, D. Olivetti
· 0 citations