Theory Lunch Seminar

Ph.D. Student
Computer Science Department
Columbia University
A Polynomial Lower Bound for Monotonicity Testing of Boolean Functions
Wednesday, February 19, 2014 - 12:00pm to 1:00pm
Gates&Hillman Centers

We prove a \tilde{\Omega}(n^{1/5}) lower bound on the query complexity of any non-adaptive two-sided error algorithm for testing whether an unknown n-variable Boolean function is monotone versus constant-far from monotone. This gives an exponential improvement on the previous lower bound of Omega(log n) due to Fischer et al from 2002. Our approach extends to give a similar lower bound for monotonicity testing of Boolean-valued functions over certain hypergrid domains {1,2,...,m}^n.

Joint work with Rocco Servedio.

About the Speaker.

For More Information, Please Contact: