We prove a lower bound of Ω(n1/3) for the query complexity of any two-sided and adaptive algorithm that tests whether an unknown Boolean function f:{0,1}n→ {0,1} is monotone versus far from monotone. This improves the recent lower bound of Ω(n1/4) for the same problem by Belovs and Blais (STOC'16). 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.

arXiv:1702.06997ACM Symposium on Theory of Computing (STOC)Jun 15, 201742 citations

ACM Symposium on Theory of Computing (STOC)

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

Mark Chen, Xi Chen, Hao Cui, William Pires, Jonah Stockwell

Published Jun 9, 2026• 0 citations

Publisher

DOI: 10.1145/3798129.3800775

Related papers

Approximating the Influence of Monotone Boolean Functions in $O(\sqrt{n})$ Query ComplexityApproximating the Influence of Monotone Boolean Functions in $O(\sqrt{n})$ Query Complexity

Dana Ron, Ronitt Rubinfeld, Muli Safra +1 more

Lecture notes in computer scienceJan 1, 20112 citations

Approximating the influence of monotone boolean functions in O(√n) query complexity

Dana Ron, Ronitt Rubinfeld, Muli Safra +1 more

International Workshop and International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and TechniquesAug 17, 20113 citations

Boolean function monotonicity testing requires (almost) $n^{1/2}$ queriesBoolean function monotonicity testing requires (almost) $n^{1/2}$ queries

Chen, Mark, Xi Chen, Hao Xuan Cui +2 more

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 $\tildeΩ(n^{1/3})$ lower bound of [CWX17] and almost matches the $\tilde{O}(\sqrt{n})$ upper bound of [KMS18].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 $\tildeΩ(n^{1/3})$ lower bound of [CWX17] and almost matches the $\tilde{O}(\sqrt{n})$ upper bound of [KMS18].

arXiv:2511.04558Nov 6, 20250 citations

Testing Classical Properties from Quantum Data

Matthias C. Caro, Naik, Preksha, Joseph Slote

Many properties of Boolean functions can be tested far more efficiently than the function itself can be learned. However, this dramatic advantage often disappears when testers are limited to random samples of f instead of adaptively chosen queries to f. In this work we investigate the quantum version of this restriction: quantum algorithms that test properties of a Boolean function f solely from copies of either the function state |f⟩∝ ∑_x|x,f(x)⟩ or the phase state |(-1)^f⟩∝ ∑_x (-1)^{f(x)}|x⟩. Quantum advantage in testing from data. For monotonicity, symmetry, and triangle-freeness, we show passive quantum testers are unboundedly or super-polynomially better than their classical passive testing counterparts. They are competitive with classic query-based testers in each case. Inadequacy of Fourier sampling. Our new testers use techniques beyond quantum Fourier sampling, and it turns out this is necessary: we show a certain class of bent functions can be tested from 𝒪(1) function states but has a sample complexity lower bound of 2^{Ω(n)} for any tester relying exclusively on Fourier and classical samples. Classical queries vs. quantum data. Our passive quantum testers are competitive with classical query-based testers, but this isn't universal: we exhibit a testing problem that can be solved from 𝒪(1) classical queries but requires Ω(2^{n/2}) function state copies. The Forrelation problem provides a separation of the same magnitude in the opposite direction, so we conclude that quantum data and classical queries are "maximally incomparable" resources for testing. Towards lower bounds. We also begin the study of lower bounds for testing from quantum data. For quantum monotonicity testing, we prove that the ensembles of [Goldreich et al., 2000; Black, 2024], which give exponential lower bounds for classical sample-based testing, do not yield any nontrivial lower bounds for testing from quantum data. New insights specific to quantum data will be required for proving copy complexity lower bounds for testing in this model.Many properties of Boolean functions can be tested far more efficiently than the function itself can be learned. However, this dramatic advantage often disappears when testers are limited to random samples of f instead of adaptively chosen queries to f. In this work we investigate the quantum version of this restriction: quantum algorithms that test properties of a Boolean function f solely from copies of either the function state |f⟩∝ ∑_x|x,f(x)⟩ or the phase state |(-1)^f⟩∝ ∑_x (-1)^{f(x)}|x⟩. Quantum advantage in testing from data. For monotonicity, symmetry, and triangle-freeness, we show passive quantum testers are unboundedly or super-polynomially better than their classical passive testing counterparts. They are competitive with classic query-based testers in each case. Inadequacy of Fourier sampling. Our new testers use techniques beyond quantum Fourier sampling, and it turns out this is necessary: we show a certain class of bent functions can be tested from 𝒪(1) function states but has a sample complexity lower bound of 2^{Ω(n)} for any tester relying exclusively on Fourier and classical samples. Classical queries vs. quantum data. Our passive quantum testers are competitive with classical query-based testers, but this isn't universal: we exhibit a testing problem that can be solved from 𝒪(1) classical queries but requires Ω(2^{n/2}) function state copies. The Forrelation problem provides a separation of the same magnitude in the opposite direction, so we conclude that quantum data and classical queries are "maximally incomparable" resources for testing. Towards lower bounds. We also begin the study of lower bounds for testing from quantum data. For quantum monotonicity testing, we prove that the ensembles of [Goldreich et al., 2000; Black, 2024], which give exponential lower bounds for classical sample-based testing, do not yield any nontrivial lower bounds for testing from quantum data. New insights specific to quantum data will be required for proving copy complexity lower bounds for testing in this model.

arXiv:2411.12730Leibniz international proceedings in informaticsNov 19, 20240 citations

Simple bounds for Boolean quadratic problems

Yurii E. Nesterov

Jan 1, 20091 citation

Beyond Talagrand functions: new lower bounds for testing monotonicity and unateness

Xi Chen, Erik Waingarten, Jinyu Xie

arXiv:1702.06997ACM Symposium on Theory of Computing (STOC)Jun 15, 201742 citations

Approximating the Influence of Monotone Boolean Functions in

O(\sqrt{n})

Query Complexity

Boolean function monotonicity testing requires (almost)

n^{1/2}

queries

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

\tildeΩ(n^{1/3})

lower bound of [CWX17] and almost matches the

\tilde{O}(\sqrt{n})

upper bound of [KMS18].