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

2014/12/17 by Xi Chen, Chen, Xi, Anindya De +5 · 1 citation
Computer Science · #Algorithms and Data Compression #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Machine Learning and Algorithms

paper · pdf · doi:10.48550/arxiv.1412.5657

openalex publication_date 2014/12/17 · openalex created_date 2019/06/27 · openalex updated_date 2026/07/28

Abstract

We prove a lower bound of Ω(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 Ω(n^1/5) lower bound for the same problem that was recently given in [CST14] and is very close to Ω(n^1/2), which we conjecture is the optimal lower bound for this model.

Cited by

• A Distance Amplification Lemma for Monotonicity

Related

• Boolean function monotonicity testing requires (almost) n^1/2 queries
• New algorithms and lower bounds for monotonicity testing
• A Polynomial Lower Bound for Testing Monotonicity
• Beyond Talagrand Functions: New Lower Bounds for Testing Monotonicity and Unateness
• Adaptivity is exponentially powerful for testing monotonicity of halfspaces