An $\widetilde{O}(n)$ Queries Adaptive Tester for Unateness
Subhash Khot, Igor Shinkar · arXiv (Cornell University) · 2016
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)/ε)$ adaptive queries to the function. The tester always accepts a unate function, and rejects with probability at least 0.9 if a function is $ε$-far from being unate.