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