12 papers
No Truly Sublogarithmic-Round Algorithm for Distributed MIS in the LOCAL Model
Seri Khoury, Aaron Schild
We prove that -round randomized LOCAL algorithms find a maximal independent set (MIS) with subconstant probability on some input. This shows that the…
On the Randomized Locality of Matching Problems in Regular Graphs
Seri Khoury, Manish Purohit, Aaron Schild +1
The main goal in distributed symmetry-breaking is to understand the locality of problems; i.e., the radius of the neighborhood that a node needs to explore in order to arrive at it…
Round Elimination via Self-Reduction: Closing Gaps for Distributed Maximal Matching
Seri Khoury, Aaron Schild
In this work, we present an lower bound for Maximal Matching (MM) in -ary trees against randomized algorithms. By a folklore reduct…
Breaking Barriers for Distributed MIS by Faster Degree Reduction
Seri Khoury, Aaron Schild
We study the problem of finding a maximal independent set (MIS) in the standard LOCAL model of distributed computing. Classical algorithms by Luby [JACM'86] and Alon, Babai, and It…
Listing 4-Cycles
Amir Abboud, Seri Khoury, Oree Leibowitz +1
In this note we present an algorithm that lists all -cycles in a graph in time where is their number. Notably, this separates -cycle list…
Hardness of Approximation in P via Short Cycle Removal: Cycle Detection, Distance Oracles, and Beyond
Amir Abboud, Karl Bringmann, Seri Khoury +1
We present a new technique for efficiently removing almost all short cycles in a graph without unintentionally removing its triangles. Consequently, triangle finding problems do no…
Beyond Alice and Bob: Improved Inapproximability for Maximum Independent Set in CONGEST
Yuval Efron, Ofer Grossman, Seri Khoury
By far the most fruitful technique for showing lower bounds for the CONGEST model is reductions to two-party communication complexity. This technique has yielded nearly tight resul…
Improved Distributed Approximations for Maximum Independent Set
Ken-ichi Kawarabayashi, Seri Khoury, Aaron Schild +1
We present improved results for approximating maximum-weight independent set ($\MaxIS$) in the CONGEST and LOCAL models of distributed computing. Given an input graph, let and…
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…
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…
Quadratic and Near-Quadratic Lower Bounds for the CONGEST Model
Keren Censor-Hillel, Seri Khoury, Ami Paz
We present the first super-linear lower bounds for natural graph problems in the CONGEST model, answering a long-standing open question. Specifically, we show that any exact comput…
Near-Linear Lower Bounds for Distributed Distance Computations, Even in Sparse Networks
Amir Abboud, Keren Censor-Hillel, Seri Khoury
We develop a new technique for constructing sparse graphs that allow us to prove near-linear lower bounds on the round complexity of computing distances in the CONGEST model. Speci…