8 papers · 1 filter
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…
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…