@inproceedings{c83f19929223495f85e936bc14787abd,
title = "A polynomial lower bound for testing monotonicity",
abstract = "We show that every algorithm for testing n-variate Boolean functions for monotonicity has query complexity Ω(n1/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 Ω(logn). Combined with the query complexity of the non-adaptive 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 non-adaptive algorithms for testing regular linear threshold functions (LTFs) for monotonicity. Chen, De, Servedio, and Tan (STOC 2015) recently showed that non-adaptive algorithms require almost Ω(n1/2) queries for this task. We introduce a new adaptive monotonicity testing algorithm which has query complexity O(logn) when the input is a regular LTF.",
keywords = "Adaptivity of query algorithms, Property testing, Talagrand's Random DNF",
author = "Aleksandrs Belovs and Eric Blais",
year = "2016",
month = jun,
day = "19",
doi = "10.1145/2897518.2897567",
language = "English",
series = "Proceedings of the Annual ACM Symposium on Theory of Computing",
publisher = "Association for Computing Machinery ",
pages = "1021--1032",
editor = "Yishay Mansour and Daniel Wichs",
booktitle = "STOC 2016 - Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing",
address = "United States",
note = "48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016 ; Conference date: 19-06-2016 Through 21-06-2016",
}