## A Polynomial Lower Bound for Testing Monotonicity

by Aleksandrs Belovs and Eric Blais

#### Oded's comments

The main result is an $\tilde\Omega(\ell^{1/4})$ lower bound
on query complexity of general testers for monotonicity
of $\ell$-variate Boolean functions. Prior results established
that the query complexity of *non-adaptive* testers for this
property is $\tilde\Theta({\sqrt\ell})$.

This is quite a feast, given that the problem was open for
more than two decades (albeit it is not fully resolved yet).
The paper also provides an explanation as to the failure
of prior attempts to establish a lower bound in this ball-park:
The type of distributions that were used for demonstrating the
lower bounds via an indistinguishability argument, can be distinguished
by an *adaptive* algorithm of logarithmic query complexity.

#### The original abstract

See the
program webpage of STOC'16.

Back to
list of Oded's choices.