Abstract | ||
---|---|---|
We show that every algorithm for testing n-variate Boolean functions for monotonicityhas query complexity Ω(n1/4). All previous lower bounds for this problem were designed for non-adaptive 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. |
Year | DOI | Venue |
---|---|---|
2016 | 10.1145/2897518.2897567 | STOC |
Keywords | DocType | Volume |
Property Testing,Adaptivity of query algorithms,Talagrand's Random DNF | Conference | abs/1511.05053 |
ISSN | Citations | PageRank |
0737-8017 | 11 | 0.73 |
References | Authors | |
15 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Aleksandrs Belovs | 1 | 131 | 14.50 |
Eric Blais | 2 | 286 | 22.49 |