Testing unateness nearly optimally

We present an Õ( n 2/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 Ω( n 2/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.

Authors

• Xi Chen 0001
• Erik Waingarten

Keywords

• Boolean functions
• unateness
• Property testing