LFCS Seminar: Thursday 2nd April: Xi Chen | LFCS

Thur, 02 Apr, 2.10pm

Venue: IF G.03

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

Abstract

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 of

directed 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).