A ${o(n)}$ monotonicity tester for Boolean functions over the hypercube

It was know that this property (of objects of size $2^n$) can be tested in $O(n/\eps)$ queries. In fact, the tester that selects $O(n/\eps)$ random edges of the hypercube and checks for violation on individual edges will do. It has been conjectured that one can do better by utilizing random "path checks", where each such check consists of a pair of comparable elements (i.e., vertices with a directed path from the lower one to the higher one). The current work proves this conjecture, but leaves open the question of whether query complexity $\sqrt(n)/\poly(\eps)$ is achievable.

Errata (18/6/13): The complexity bound was corrected to $\widetilde{O}(n^{7/8}\eps^{-c})$, for some $c\in(1,2)$ which I don't recall. The point is that the exponent of $n$ is a constant smaller than 1.

Addendum (21/6/13): The analysis relies on an isoperimetric inequality regarding the directed hypercube, and its connection to the edge and path tests. Specifically, the edge test rejects with probability that equals the number of violating edges (i.e., directed edge expansion of the set $f^{-1}(1)$), which in turn is between $\e$ and $\e/n$, where $\e$ is the distance of $f$ to the property. Hence, if the number of violating edges is not too small (i.e., is greater than $\e/n^{0.99}$), then the edge test will do. Otherwise, the directed vertex expansion must be larger (i.e., larger than $\e/n^{0.4}$ or so), or rather the set of violating edges must contain a relatively large matching. In this case, the path tester can be shown to reject with probability at least $\e/n^{0.9}$ (or so). (The isoperimetric inequality asserts that the product of the directed edge expansion and the "matched expansion" is lower bounded in terms of $\e^2$.)

The original abstract

See ECCC TR13-029

Given oracle access to a Boolean function $f:\{0,1\}^n \mapsto \{0,1\}$, we design a randomized tester that takes as input a parameter $\eps>0$, and outputs "Yes" if the function is monotone, and outputs "No" with probability at least $2/3$, if the function is $\eps$-far from monotone. That is, $f$ needs to be modified at $\eps$-fraction of the points to make it monotone. Our non-adaptive, one-sided tester makes $\widetilde{O}(n^{5/6}\eps^{-5/3})$ queries to the oracle.

Back to list of Oded's choices.