Beyond Talagrand Functions: New Lower Bounds for Testing Monotonicity and Unateness

2017/02/22 by Xi Chen, Chen, Xi, Erik Waingarten +3 · 4 citations
Computer Science · #Complexity and Algorithms in Graphs #Machine Learning and Algorithms #Cryptography and Data Security

paper · pdf · doi:10.48550/arxiv.1702.06997

Abstract

We prove a lower bound of Ω(n^1/3) for the query complexity of any two-sided and adaptive algorithm that tests whether an unknown Boolean function f:\0,1\ⁿ→ \0,1\ is monotone or far from monotone. This improves the recent bound of Ω(n^1/4) for the same problem by Belovs and Blais [BB15]. Our result builds on a new family of random Boolean functions that can be viewed as a two-level extension of Talagrand's random DNFs. Beyond monotonicity, we also prove a lower bound of Ω(n^2/3) for any two-sided and adaptive algorithm, and a lower bound of Ω(n) for any one-sided and non-adaptive algorithm for testing unateness, a natural generalization of monotonicity. The latter matches the recent linear upper bounds by Khot and Shinkar [KS15] and by Chakrabarty and Seshadhri [CS16].

Cited by

• A Distance Amplification Lemma for Monotonicity
• Testing noisy low-degree polynomials for sparsity
• Halfspaces are hard to test with relative error
• Relative-error unateness testing

Related

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