Approximating the Distance to Monotonicity of Boolean Functions

Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Erik Waingarten

We design a nonadaptive algorithm that, given oracle access to a function $f:\{0,1{\}}^n\to \{0,1\}$ which is $\alpha$-far from monotone, makes poly$(n,1/\alpha )$ queries and returns an est…