1 citations · 2 across the 7 of their papers we have counts for
6 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…
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…
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…
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…