92 citations · 120 across the 20 of their papers we have counts for
5 papers · 1 filter
Trade-offs in Distributed Interactive Proofs
Pierluigi Crescenzi, Pierre Fraigniaud, Ami Paz
The study of interactive proofs in the context of distributed network computing is a novel topic, recently introduced by Kol, Oshman, and Saxena [PODC 2018]. In the spirit of seque…
A Topological Perspective on Distributed Network Algorithms
Armando Castañeda, Pierre Fraigniaud, Ami Paz +3
More than two decades ago, combinatorial topology was shown to be useful for analyzing distributed fault-tolerant algorithms in shared memory systems and in message passing systems…
Hardness of Distributed Optimization
Nir Bachrach, Keren Censor-Hillel, Michal Dory +3
This paper studies lower bounds for fundamental optimization problems in the CONGEST model. We show that solving problems exactly in this model can be a hard task, by providing $\t…
Smaller Cuts, Higher Lower Bounds
Amir Abboud, Keren Censor-Hillel, Seri Khoury +1
This paper proves strong lower bounds for distributed computing in the CONGEST model, by presenting the bit-gadget: a new technique for constructing graphs with small cuts. The con…
Fast Deterministic Algorithms for Highly-Dynamic Networks
Keren Censor-Hillel, Neta Dafni, Victor I. Kolobov +2
This paper provides an algorithmic framework for obtaining fast distributed algorithms for a highly-dynamic setting, in which *arbitrarily many* edge changes may occur in each roun…