**Speaker: ****Eric Blais**, University of Waterloo

**Title:** A Polynomial Lower Bound for Testing Monotonicity

**Abstract:**

One of the fundamental problems in property testing is the monotonicity testing problem: how many values of some Boolean function f : {0,1}^n -> {0,1} must we query to distinguish monotone functions from those that are far from monotone? In 1998, Goldreich, Goldwasser, Lehman, and Ron showed that a simple algorithm which checks that the function is monotone on edges of the Boolean hypercube is a valid monotonicity tester with query complexity O(n). Until very recently, however, we didn’t know if any other algorithm could test monotonicity with fewer queries and, in fact, the best lower bound for the query complexity of testers was only Omega(log log n). (!)

A recent flurry of activity has dramatically improved our knowledge on this problem: we now know that it is possible to test monotonicity with O(sqrt{n}) queries (Khot, Minzer, and Safra ’15) and that this query complexity is optimal for all non-adaptive algorithms (Chen, De, Servedio, and Tan ’15). These results left open one important question: is it still possible to reduce the query complexity by an exponential amount if we allow the algorithm to adaptively choose its queries based on the previous values observed? In this talk, we will discuss a recent result obtained with Alexander Belov that gives a negative answer to this question.