Boolean function monotonicity testing requires (almost) n^1/2 non-adaptive queries

DOI10.1145/2746539.2746570MaRDI QIDQ2941544zbMATH OpenOpenAlexFDO

Authors Xi Chen, Anindya De, Li-Yang Tan, Rocco A. Servedio

Publication date 21 August 2015

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

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

zbMATH Keywords

Boolean functionsmonotonicity testingproperty testing

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 prove a lower bound of $Omega(n^{1/2-c})$, for all $c>0$, on the query complexity of (two-sided error) non-adaptive algorithms for testing whether an $n$-variable Boolean function is monotone versus constant-far from monotone. This improves a $ildeOmega(n^{1/5})$ lower bound for the same problem that was recently given in [CST14] and is very close to $Omega(n^{1/2})$, which we conjecture is the optimal lower bound for this model.

Recommendations

• A polynomial lower bound for testing monotonicity
• A polynomial lower bound for testing monotonicity
• Beyond Talagrand functions: new lower bounds for testing monotonicity and unateness
• Approximating the distance to monotonicity of Boolean functions
• On Monotonicity Testing and Boolean Isoperimetric-type Theorems

Cites work

• Approximate distance oracles
• Approximate distance oracles with constant query time
• Automata, Languages and Programming
• Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
• Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
• Fast C-K-R partitions of sparse graphs
• Near-Linear Time Construction of Sparse Neighborhood Covers
• On approximate distance labels and routing schemes with affine stretch
• On sparse spanners of weighted graphs
• Ramsey partitions and proximity data structures
• Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
• Shortest-path queries in static networks

Cited in

(37)

• A large lower bound on the query complexity of a simple Boolean function
• Gaussian bounds for noise correlation of resilient functions
• Exponentially improved algorithms and lower bounds for testing signed majorities
• An optimal tester for k-Linear
• An o(n) monotonicity tester for Boolean functions over the hypercube
• Monotonicity checking
• On Monotonicity Testing and Boolean Isoperimetric-type Theorems
• An O(n) queries adaptive tester for unateness
• Parameterized property testing of functions
• Testing k-monotonicity
• Beyond Talagrand functions: new lower bounds for testing monotonicity and unateness
• The query complexity of witness finding
• 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
• Adaptive Boolean Monotonicity Testing in Total Influence Time
• Almost optimal distribution-free junta testing
• Optimal unateness testers for real-valued functions: adaptivity helps
• Approximating the distance to monotonicity of Boolean functions
• Testing unateness nearly optimally
• Flipping out with many flips: hardness of testing \(k\)-monotonicity
• A polynomial lower bound for testing monotonicity
• A \(o(n)\) monotonicity tester for Boolean functions over the hypercube
• Monotonicity Checking
• Exponentially improved algorithms and lower bounds for testing signed majorities
• On Monotonicity Testing and the 2-to-2 Games Conjecture
• Testing monotonicity
• Almost Optimal Distribution-Free Sample-Based Testing of k-Modality
• Approximating the distance to monotonicity of Boolean functions
• Almost Optimal Testers for Concise Representations.
• Directed isoperimetric theorems for Boolean functions on the hypergrid and an \(\widetilde{O}(n\sqrt{d})\) monotonicity tester
• Isoperimetric inequalities for real-valued functions with applications to monotonicity testing
• Testing intersecting and union-closed families
• Nearly optimal bounds for sample-based testing and learning of k-monotone functions
• A \(d^{1/2+o(1)}\) monotonicity tester for Boolean functions on \(d\)-dimensional hypergrids
• Relative-error testing of conjunctions and decision lists
• Property testing of the Boolean and binary rank

This page was built for publication: Boolean function monotonicity testing requires (almost) \(n^{1/2}\) non-adaptive queries

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