4 papers
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…
Stochastic Vertex Cover with Few Queries
Soheil Behnezhad, Avrim Blum, Mahsa Derakhshan
We study the minimum vertex cover problem in the following stochastic setting. Let be an arbitrary given graph, a parameter of the problem, and let be a ra…