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

Deeparnab Chakrabarty and C. Seshadhri

#### Oded's comments

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.