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