Soheil Behnezhad

Streaming Algorithms for Monotonicity Testing

The main result is an algorithm that $(1+\epsilon)$-approximates distance to monotonicity in $\sqrt{n}^{1+o(1)}$ passes, and it is proved that this is the best pass-complexity one can hope for, for any $O(1)$-approximation, short of improving the state-of-the-art streaming algorithm for st-reachability.