A polynomial lower bound for monotonicity testing of Boolean functions over hypercube and hypergrid domains

Computer Science/Discrete Mathematics Seminar I
Topic:A polynomial lower bound for monotonicity testing of Boolean functions over hypercube and hypergrid domains
Speaker:Rocco Servedio
Affiliation:Columbia University
Date:Monday, March 31
Time/Room:11:15am - 12:15pm/West Bldg. Lect. Hall
Video Link:https://video.ias.edu/csdm/2014/0331-RoccoServedio

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 Li-Yang Tan.