12 citations · 29 across the 37 of their papers we have counts for
6 papers · 1 filter
Sublinear Time Algorithms and Complexity of Approximate Maximum Matching
Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein
Sublinear time algorithms for approximating maximum matching size have long been studied. Much of the progress over the last two decades on this problem has been on the algorithmic…
On Regularity Lemma and Barriers in Streaming and Dynamic Matching
Sepehr Assadi, Soheil Behnezhad, Sanjeev Khanna +1
We present a new approach for finding matchings in dense graphs by building on Szemerédi's celebrated Regularity Lemma. This allows us to obtain non-trivial albeit slight improveme…
Dynamic Algorithms for Maximum Matching Size
Soheil Behnezhad
We study fully dynamic algorithms for maximum matching. This is a well-studied problem, known to admit several update-time/approximation trade-offs. For instance, it is known how t…
Beating Greedy Matching in Sublinear Time
Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein +1
We study sublinear time algorithms for estimating the size of maximum matching in graphs. Our main result is a -approximation algorithm which can be implemented…
Almost 3-Approximate Correlation Clustering in Constant Rounds
Soheil Behnezhad, Moses Charikar, Weiyun Ma +1
We study parallel algorithms for correlation clustering. Each pair among objects is labeled as either "similar" or "dissimilar". The goal is to partition the objects into arbit…
New Trade-Offs for Fully Dynamic Matching via Hierarchical EDCS
Soheil Behnezhad, Sanjeev Khanna
We study the maximum matching problem in fully dynamic graphs: a graph is undergoing both edge insertions and deletions, and the goal is to efficiently maintain a large matching af…