Streaming Algorithms for Monotonicity Testing

Amir Azarmehr, Soheil Behnezhad, Lily Chung +3

Consider a poset - or equivalently an $n$-vertex DAG $G=(V,E)$ - and a boolean function $f:V\to \{0,1\}$ on its vertex set. We say $f$ is monotone if $f(u)\le f(v)$ f…