Testing Unateness Nearly Optimally

We present an tildeO(n2/3/ε2)-query algorithm that tests whether an unknown Boolean function fcolon0,1nrightarrow 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 tildeOmega(n2/3) lower~bound of [CWX17a]. The algorithm builds on a novel use of the binary search procedure and its analysis over long random paths.