12 citations · 29 across the 37 of their papers we have counts for
48 papers
Streaming Algorithms for Monotonicity Testing
Amir Azarmehr, Soheil Behnezhad, Lily Chung +3
Consider a poset - or equivalently an -vertex DAG - and a boolean function on its vertex set. We say is monotone if f…
Single-Pass Streaming CSPs via Two-Tier Sampling
Amir Azarmehr, Soheil Behnezhad, Shane Ferrante
We study the maximum constraint satisfaction problem, Max-CSP, in the streaming setting. Given variables, the constraints arrive sequentially in an arbitrary order, with each c…
Caterpillar of Thoughts: The Optimal Test-Time Algorithm for Large Language Models
Amir Azarmehr, Soheil Behnezhad, Alma Ghafari
Large language models (LLMs) can often produce substantially better outputs when allowed to use additional test-time computation, such as sampling, chain of thought, backtracking,…
Markov Chains with Rewinding
Amir Azarmehr, Soheil Behnezhad, Alma Ghafari +1
Motivated by techniques developed in recent progress on lower bounds for sublinear time algorithms (Behnezhad, Roghani and Rubinstein, STOC 2023, FOCS 2023, and STOC 2024) we intro…
Half-Approximating Maximum Dicut in the Streaming Setting
Amir Azarmehr, Soheil Behnezhad, Shane Ferrante +1
We study streaming algorithms for the maximum directed cut problem. The edges of an -vertex directed graph arrive one by one in an arbitrary order, and the goal is to estimate t…
Tight Pair Query Lower Bounds for Matching and Earth Mover's Distance
Amir Azarmehr, Soheil Behnezhad, Mohammad Roghani +1
How many adjacency matrix queries (also known as pair queries) are required to estimate the size of a maximum matching in an -vertex graph ? We study this fundamental questio…
Vizing's Theorem in Deterministic Almost-Linear Time
Sepehr Assadi, Soheil Behnezhad, Sayan Bhattacharya +3
Vizing's theorem states that any -vertex -edge graph of maximum degree can be edge colored using at most different colors. Vizing's original proof is easily transl…
Lower Bounds for Non-adaptive Local Computation Algorithms
Amir Azarmehr, Soheil Behnezhad, Alma Ghafari +1
We study *non-adaptive* Local Computation Algorithms (LCA). A reduction of Parnas and Ron (TCS'07) turns any distributed algorithm into a non-adaptive LCA. Plugging known distribut…
Stochastic Matching via In-n-Out Local Computation Algorithms
Amir Azarmehr, Soheil Behnezhad, Alma Ghafari +1
Consider the following stochastic matching problem. Given a graph , an unknown subgraph is realized where includes every edge of independently…
Fully Dynamic (Δ+1) Coloring Against Adaptive Adversaries
Soheil Behnezhad, Rajmohan Rajaraman, Omer Wasim
Over the years, there has been extensive work on fully dynamic algorithms for classic graph problems that admit greedy solutions. Examples include vertex coloring, maximal…
Vizing's Theorem in Near-Linear Time
Sepehr Assadi, Soheil Behnezhad, Sayan Bhattacharya +3
Vizing's theorem states that any -vertex -edge graph of maximum degree can be edge colored using at most different colors [Vizing, 1964]. Vizing's original proof i…
Massively Parallel Minimum Spanning Tree in General Metric Spaces
Amir Azarmehr, Soheil Behnezhad, Rajesh Jayaram +3
We study the minimum spanning tree (MST) problem in the massively parallel computation (MPC) model. Our focus is particularly on the *strictly sublinear* regime of MPC where the sp…
Settling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams
Sepehr Assadi, Soheil Behnezhad, Christian Konrad +2
A semi-streaming algorithm in dynamic graph streams processes any -vertex graph by making one or multiple passes over a stream of insertions and deletions to edges of the graph…
Approximating Maximum Matching Requires Almost Quadratic Time
Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein
We study algorithms for estimating the size of maximum matching. This problem has been subject to extensive research. For -vertex graphs, Bhattacharya, Kiss, and Saranurak [FOCS…
Bipartite Matching in Massive Graphs: A Tight Analysis of EDCS
Amir Azarmehr, Soheil Behnezhad, Mohammad Roghani
Maximum matching is one of the most fundamental combinatorial optimization problems with applications in various contexts such as balanced clustering, data mining, resource allocat…
Correlation Clustering Beyond the Pivot Algorithm
Soheil Behnezhad, Moses Charikar, Vincent Cohen-Addad +2
We study the classic correlation clustering in the dynamic setting. Given objects and a complete labeling of the object-pairs as either similar or dissimilar, the goal is to pa…
Fully Dynamic Matching and Ordered Ruzsa-Szemerédi Graphs
Soheil Behnezhad, Alma Ghafari
We study the fully dynamic maximum matching problem. In this problem, the goal is to efficiently maintain an approximate maximum matching of a graph that is subject to edge inserti…
Local Computation Algorithms for Maximum Matching: New Lower Bounds
Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein
We study local computation algorithms (LCA) for maximum matching. An LCA does not return its output entirely, but reveals parts of it upon query. For matchings, each query is a ver…
Fully Dynamic Matching: -Approximation in Polylog Update Time
Amir Azarmehr, Soheil Behnezhad, Mohammad Roghani
We study maximum matchings in fully dynamic graphs, which are graphs that undergo both edge insertions and deletions. Our focus is on algorithms that estimate the size of maximum m…
Streaming Edge Coloring with Asymptotically Optimal Colors
Soheil Behnezhad, Mohammad Saneian
Given a graph , an edge-coloring is an assignment of colors to edges of such that any two edges sharing an endpoint receive different colors. By Vizing's celebrated theorem,…
Robust Communication Complexity of Matching: EDCS Achieves 5/6 Approximation
Amir Azarmehr, Soheil Behnezhad
We study the robust communication complexity of maximum matching. Edges of an arbitrary -vertex graph are randomly partitioned between Alice and Bob independently and unifor…
Sublinear Algorithms for TSP via Path Covers
Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein +1
We study sublinear time algorithms for the traveling salesman problem (TSP). First, we focus on the closely related {\em maximum path cover} problem, which asks for a collection of…
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…