Preprint
Aug 2026
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.
Amir Azarmehr, Soheil Behnezhad, Lily Chung et al.
· 0 citations