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

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 obtained in [6], and is very close to the recent upper bound of ~O(n 1/2 /ε 2 ) by Khot et al. [13].

Authors

• Xi Chen 0001
• Anindya De
• Rocco A. Servedio
• Li-Yang Tan

Keywords

• boolean functions
• monotonicity testing
• property testing