An e O(n) Queries Adaptive Tester for Unateness
Subhash Khot, Igor Shinkar · 2016
We present an adaptive tester for the unateness property of Boolean functions. Given a function f : {0,1} n → {0,1} the tester makes O(nlog(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.