TCS+ Talk

Please join us this TCS+ video seminar. Coffee and pastries will be served.

One of the earliest and most fundamental problems in property testing is monotonicity testing: how many queries to a Boolean function f : {0,1}^n -> {0,1} do we need to distinguish between the case where f is monotone and the one where f is far from monotone? Extensive study of this problem has revealed surprising connections to other topics in the analysis of Boolean functions, including directed isoperimetric inequalities and invariance principles for linear threshold functions. Yet, despite all this effort, until recently there was still an exponential gap between the best upper and lower bounds for the number of queries that general (adaptive) testers need to test monotonicity. In this talk, we will see how noise sensitivity and Talagrand's random DNF functions can be used to significantly improve the lower bound for this problem. As a result, we will see that a polynomial number of queries is both sufficient and necessary to test monotonicity. We will also discuss some related results. This is joint work with Alexander Belov.