Adaptivity Does Not Help: Nearly Tight Lower Bounds for Boolean Monotonicity Testing

Monotonicity testing asks: given a Boolean function f: {0,1}^n -> {0,1}, how many queries are needed to distinguish whether f is monotone or far from monotone? For nonadaptive algorithms, the query complexity was pinned down at \sqrt{n}. Along the way, a series ofdirected isoperimetric inequalities were established to analyze testers such as the edge tester and the path tester.

 

But can adaptivity help beat the \sqrt{n} bound? In this talk we answer in the negative, by proving an almost tight n^{0.5-c} lower bound for adaptive monotonicity testing, for any constant c > 0. Our proof is based on a multilevel extension of Talagrand's function.

 

Joint work with Mark Chen, Hao Cui, William Pires, and Jonah Stockwell (Columbia).