1 citations · 3 across the 11 of their papers we have counts for
14 papers
Metric TSP in Sublinear Time: Breaking Two Approximation
Amir Azarmehr, Soheil Behnezhad
The seminal result of Czumaj and Sohler [STOC'04] showed that a 2-approximation of the value of metric TSP can be obtained with sublinear queries. Whether sublinear algorithms can…
The Power of Two-Choice Linear Probing
Amir Azarmehr, Michael A. Bender, William Kuszmaul +1
This paper considers the following basic question: If an (ordered) linear-probing hash table is allowed \emph{two} hash functions, instead of one, how does this change the expected…
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…
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…
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…
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…
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…
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…