An $\tilde{O}(n)$ Queries Adaptive Tester for Unateness

Subhash Khot, Igor Shinkar

We present an adaptive tester for the unateness property of Boolean functions. Given a function $f:\{0,1{\}}^n\to \{0,1\}$ the tester makes $O(n\log (n)/\epsilon )$ adaptive queries to the…