Showing cs.DCShow all
3 papers · 1 filter
cs.DC2026
Distributed Lower Bounds via Automatic Self-Reduction
Alkida Balliu, Francesco d'Amore, Dennis Olivetti
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 distribu…
cs.DC2025
New Hardness Results for the LOCAL Model via a Simple Self-Reduction
Alkida Balliu, Filippo Casagrande, Francesco d'Amore +1
Very recently, Khoury and Schild [FOCS 2025] showed that any randomized LOCAL algorithm that solves maximal matching requires rounds, where is the…
cs.DC2025
Distributed Algorithms for Potential Problems
Alkida Balliu, Thomas Boudier, Francesco d'Amore +4
In this work, we present a fast distributed algorithm for local potential problems: these are graph problems where the task is to find a locally optimal solution where no node can…