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.