10 citations · 15 across the 7 of their papers we have counts for
Showing 2017Show all
3 papers · 1 filter
cs.DS2017
Fooling Views: A New Lower Bound Technique for Distributed Computations under Congestion
Amir Abboud, Keren Censor-Hillel, Seri Khoury +1
We introduce a novel lower bound technique for distributed graph algorithms under bandwidth limitations. We define the notion of \emph{fooling views} and exemplify its strength by…
cs.CC2017
Distributed PCP Theorems for Hardness of Approximation in P
Amir Abboud, Aviad Rubinstein, Ryan Williams
We present a new distributed model of probabilistically checkable proofs (PCP). A satisfying assignment to a CNF formula is shared between two parties, where…
cs.DS2017
Near-Optimal Compression for the Planar Graph Metric
Amir Abboud, Pawel Gawrychowski, Shay Mozes +1
The Planar Graph Metric Compression Problem is to compactly encode the distances among nodes in a planar graph of size . Two naïve solutions are to store the graph using $O(…