Boolean Function Monotonicity Testing Requires (Almost) n 1/2 Non-adaptive Queries

DOI10.1145/2746539.2746570zbMath1321.68300arXiv1412.5657OpenAlexW1988511047MaRDI QIDQ2941544

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 functionsproperty testingmonotonicity testing

Mathematics Subject Classification ID

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

Related Items (15)

Parameterized property testing of functions ⋮ On Monotonicity Testing and Boolean Isoperimetric-type Theorems ⋮ Approximating the distance to monotonicity of Boolean functions ⋮ An optimal tester for \(k\)-Linear ⋮ Adaptivity Is Exponentially Powerful for Testing Monotonicity of Halfspaces ⋮ Adaptive Lower Bound for Testing Monotonicity on the Line ⋮ Almost Optimal Distribution-Free Sample-Based Testing of k-Modality ⋮ Almost Optimal Testers for Concise Representations. ⋮ Gaussian bounds for noise correlation of resilient functions ⋮ Adaptive Boolean Monotonicity Testing in Total Influence Time ⋮ Almost optimal distribution-free junta testing ⋮ Unnamed Item ⋮ A Polynomial Lower Bound for Testing Monotonicity ⋮ Flipping Out with Many Flips: Hardness of Testing $k$-Monotonicity ⋮ Unnamed Item

Cites Work

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

This page was built for publication: Boolean Function Monotonicity Testing Requires (Almost) n 1/2 Non-adaptive Queries