Testing unateness nearly optimally
Xi Chen, Erik Waingarten · 2019
We present an Õ(n2/3/є2)-query algorithm that tests whether an unknown Boolean function f∶{0,1}n→ {0,1} is unate (i.e., every variable is either non-decreasing or non-increasing) or є-far from unate. The upper bound is nearly optimal given the Ω(n2/3) lower bound of Chen, Waingarten and Xie (2017). The algorithm builds on a novel use of the binary search procedure and its analysis over long random paths.