A polynomial lower bound for testing monotonicity

DOI10.1145/2897518.2897567MaRDI QIDQ5361899zbMATH OpenOpenAlexFDO

Authors Aleksandrs Belovs, Eric Blais

Publication date 29 September 2017

Published in Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1511.05053

zbMATH Keywords

adaptivity of query algorithmsproperty testingTalagrand's random DNF

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20)

Abstract: We show that every algorithm for testing $n$-variate Boolean functions for monotonicity must have query complexity $ildeOmega(n^{1/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 $Omega(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 $Omega(n^{1/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.

Recommendations

• A polynomial lower bound for testing monotonicity
• Boolean function monotonicity testing requires (almost) \(n^{1/2}\) non-adaptive queries
• Beyond Talagrand functions: new lower bounds for testing monotonicity and unateness
• Adaptive lower bound for testing monotonicity on the line
• scientific article; zbMATH DE number 1418269

Cited in

(28)

• Exponentially improved algorithms and lower bounds for testing signed majorities
• An optimal tester for k-Linear
• Boolean function monotonicity testing requires (almost) \(n^{1/2}\) non-adaptive queries
• On Monotonicity Testing and Boolean Isoperimetric-type Theorems
• Parameterized property testing of functions
• Testing k-monotonicity
• Beyond Talagrand functions: new lower bounds for testing monotonicity and unateness
• A polynomial lower bound for testing monotonicity
• Adaptivity is exponentially powerful for testing monotonicity of halfspaces
• Adaptive lower bound for testing monotonicity on the line
• Flipping out with many flips: hardness of testing \(k\)-monotonicity
• Adaptive Boolean Monotonicity Testing in Total Influence Time
• scientific article; zbMATH DE number 7559095 (Why is no real title available?)
• Almost optimal distribution-free junta testing
• Optimal unateness testers for real-valued functions: adaptivity helps
• Flipping out with many flips: hardness of testing \(k\)-monotonicity
• scientific article; zbMATH DE number 6395191 (Why is no real title available?)
• Exponentially improved algorithms and lower bounds for testing signed majorities
• Approximating the Noise Sensitivity of a Monotone Boolean Function
• Almost Optimal Distribution-Free Sample-Based Testing of k-Modality
• Approximating the distance to monotonicity of Boolean functions
• Almost Optimal Testers for Concise Representations.
• Isoperimetric inequalities for real-valued functions with applications to monotonicity testing
• Testing intersecting and union-closed families
• Testing and learning convex sets in the ternary hypercube
• Nearly optimal bounds for sample-based testing and learning of k-monotone functions
• Agnostic proper learning of monotone functions: beyond the black-box correction barrier
• Relative-error testing of conjunctions and decision lists

This page was built for publication: A polynomial lower bound for testing monotonicity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5361899)