12 citations · 29 across the 37 of their papers we have counts for
4 papers · 1 filter
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…