Paper Info
Title
A Polynomial Lower Bound For Testing Monotonicity
Abstract
We show that every algorithm for testing n-variate Boolean functions for monotonicity must have query complexity (Omega) over tilde (n(1/4)). All previous lower bounds for this problem were designed for nonadaptive algorithms and, as a result, the best previous lower bound for general (possibly adaptive) monotonicity testers was only Omega(log n). Combined with the query complexity of the nonadaptive monotonicity tester of Khot, Minzer, and Safra (FOCS 2015), our lower bound shows that adaptivity can result in at most a quadratic reduction in the query complexity for testing monotonicity. By contrast, we show that there is an exponential gap between the query complexity of adaptive and nonadaptive algorithms for testing regular linear threshold functions (LTFs) for monotonicity. Chen, De, Servedio, and Tan (STOC 2015) recently showed that nonadaptive algorithms require almost Omega(n(1/2)) queries for this task. We introduce a new adaptive monotonicity testing algorithm which has query complexity Omega(log n) when the input is a regular LTF.
Year
DOI
Venue
2021
10.1137/16M1097006
SIAM JOURNAL ON COMPUTING
Keywords
DocType
Volume
property testing, monotone Boolean functions, noise sensitivity, Talagrand's random CNF
Journal
50
Issue
ISSN
Citations 
3
0097-5397
0
PageRank 
References 
Authors
0.34
0
2
Name
Order
Citations
PageRank
Aleksandrs Belovs113114.50
Eric Blais228622.49