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

2025/11/06 by Mark Chen, Chen, Mark, Xi Chen +7 · 1 voice · 1 citation
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Machine Learning and Algorithms #cs.CC #cs.DM #cs.DS

paper · pdf · doi:10.48550/arxiv.2511.04558

openalex publication_date 2025/11/06 · arxiv published 2025/11/06 · arxiv updated 2025/11/07 · openalex created_date 2025/11/08 · openalex updated_date 2026/07/28

Abstract

We show that for any constant c>0, any (two-sided error) adaptive algorithm for testing monotonicity of Boolean functions must have query complexity Ω(n^1/2-c). This improves the Ω(n^1/3) lower bound of [CWX17] and almost matches the O(√(n)) upper bound of [KMS18].

Cited by

• A Distance Amplification Lemma for Monotonicity

Discussions

• A very exciting result!! arxiv.org/pdf/2511.045... [bsky, 3 points, 0 comments]

Related

• Boolean function monotonicity testing requires (almost) n^1/2 non-adaptive queries
• A Polynomial Lower Bound for Testing Monotonicity
• New algorithms and lower bounds for monotonicity testing
• Beyond Talagrand Functions: New Lower Bounds for Testing Monotonicity and Unateness
• Adaptive Lower Bound for Testing Monotonicity on the Line