Boolean Unateness Testing with $\tilde{O}(n^{3/4})$ Adaptive Queries

Abstract

We give an adaptive algorithm which tests whether an unknown Boolean function $f:\{0,1{\}}^n\to \{0,1\}$ is unate, i.e. every variable of $f$ is either non-decreasing or non-increasing, or $\epsilon$-far from unate with one-sided error using $\tilde{O}(n^{3/4}/{\epsilon }^2)$ queries. This improves on the best adaptive $O(n/\epsilon )$-query algorithm from Baleshzar, Chakrabarty, Pallavoor, Raskhodnikova and Seshadhri when $1/\epsilon \ll n^{1/4}$. Combined with the $\tilde{\Omega }(n)$-query lower bound for non-adaptive algorithms with one-sided error of [CWX17, BCPRS17], we conclude that adaptivity helps for the testing of unateness with one-sided error. A crucial component of our algorithm is a new subroutine for finding bi-chromatic edges in the Boolean hypercube called adaptive edge search.

References in corpus (4)

• New algorithms and lower bounds for monotonicity testing
• Testing Unateness of Real-Valued Functions
• A $\tilde{O}(n)$ Non-Adaptive Tester for Unateness
• A Lower Bound for Nonadaptive, One-Sided Error Testing of Unateness of Boolean Functions over the Hypercube