Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2511.04558

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

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

Published Nov 6, 2025• 2 citations
arXivHTMLPDF

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

DOI
10.48550/arxiv.2511.04558

Related papers

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

Xi Chen, Erik Waingarten, Jinyu Xie

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.06997•ACM Symposium on Theory of Computing (STOC)•Jun 15, 2017•55 citations

Relative-Error Unateness Testing

Xi Chen, Diptaksho Palit, Kabir Peshawaria +3 more

The model of relative-error property testing of Boolean functions has been the subject of significant recent research effort [CDH+24][CPPS25a][CPPS25b] In this paper we consider the problem of relative-error testing an unknown and arbitrary $f: \{0,1\}^n \to \{0,1\}$ for the property of being a unate function, i.e. a function that is either monotone non-increasing or monotone non-decreasing in each of the $n$ input variables. Our first result is a one-sided non-adaptive algorithm for this problem that makes $\tilde{O}(\log(N)/ε)$ samples and queries, where $N=|f^{-1}(1)|$ is the number of satisfying assignments of the function that is being tested and the value of $N$ is given as an input parameter to the algorithm. Building on this algorithm, we next give a one-sided adaptive algorithm for this problem that does not need to be given the value of $N$ and with high probability makes $\tilde{O}(\log(N)/ε)$ samples and queries. We also give lower bounds for both adaptive and non-adaptive two-sided algorithms that are given the value of $N$ up to a constant multiplicative factor. In the non-adaptive case, our lower bounds essentially match the complexity of the algorithm that we provide.

arXiv:2510.21589•Leibniz international proceedings in informatics•Oct 24, 2025•2 citations

Adaptivity Is Exponentially Powerful for Testing Monotonicity of Halfspaces

Xi Chen, Rocco A. Servedio, Li-Yang Tan +1 more

We give a poly(log(n),1/epsilon)-query adaptive algorithm for testing whether an unknown Boolean function f:{-1, 1}^n -> {-1, 1}, which is promised to be a halfspace, is monotone versus epsilon-far from monotone. Since non-adaptive algorithms are known to require almost Omega(n^{1/2}) queries to test whether an unknown halfspace is monotone versus far from monotone, this shows that adaptivity enables an exponential improvement in the query complexity of monotonicity testing for halfspaces.

arXiv:1706.05556•Leibniz international proceedings in informatics•Jan 1, 2017•1 citation

Approximating the Influence of Monotone Boolean Functions in O(√n) Query Complexity

Dana Ron, Ronitt Rubinfeld, Muli Safra +2 more

The Total Influence ( Average Sensitivity ) of a discrete function is one of its fundamental measures. We study the problem of approximating the total influence of a monotone Boolean function, which we denote by I [ f ]. We present a randomized algorithm that approximates the influence of such functions to within a multiplicative factor of (1 ± ε ) by performing O (√ n I [ f ] poly(1/ ε )) queries. We also prove a lower bound of Ω (√ n log n · I [ f ]) on the query complexity of any constant factor approximation algorithm for this problem (which holds for I [ f ]= Ω (1)), hence showing that our algorithm is almost optimal in terms of its dependence on n . For general functions, we give a lower bound of Ω ( n I [ f ]), which matches the complexity of a simple sampling algorithm.

arXiv:1101.5345•ACM Transactions on Computation Theory•Nov 1, 2012•29 citations

A Unified Lower Bound on the Noisy Query Complexity of Boolean Functions

Yuzhou Gu, Xin Li, Yinzhan Xu

We study the query complexity of Boolean functions $f: \{0, 1\}^n \rightarrow \{0, 1\}$ in the noisy query model introduced by Feige, Raghavan, Peleg and Upfal [SICOMP 1994]. In this model, an algorithm can adaptively query the bits of an input vector, but each query result is independently flipped with constant probability $p \in (0, 1/2)$; repeated queries are allowed. The noisy query complexity $\mathsf{N}_p(f)$ of a function $f$ is defined as the minimum expected number of queries needed to compute $f(x)$ with error probability at most $1/3$, for the worst case input $x$. We prove a general lower bound on $\mathsf{N}_p(f)$ based on degree statistics of certain subgraphs of the Boolean hypercube. This is the first general lower bound beyond those implied by the simple observation that $\mathsf{N}_p(f)$ is lower bounded by the randomized query complexity. We show that this recovers (up to a constant factor) most previously known lower bounds on the noisy query complexity of Boolean functions, providing a unified framework for understanding these results and simplifying the proofs in several cases. Furthermore, this resolves in the affirmative an open problem of Gu, Li and Xu [COLT 2025] that $\mathsf{N}_p(f) = Ω(\mathsf{I}(f) \log \mathsf{I}(f))$, where $\mathsf{I}(f)$ denotes the total influence of $f$. We also apply our general lower bound to obtain tight bounds on the noisy query complexity for several new functions.

arXiv:2606.11448•Jun 9, 2026•0 citations

Quantum Algorithm for Monotonicity Testing on the Hypercube

Aleksandrs Belovs, Eric Blais

In this note, we develop a bounded-error quantum algorithm that makes $\tilde O(n^{1/4}\varepsilon^{-1/2})$ queries to a Boolean function $f$, accepts a monotone function, and rejects a function that is $\varepsilon$-far from being monotone. This gives a super-quadratic improvement compared to the best known randomized algorithm for all $\varepsilon = o(1)$. The improvement is cubic when $\varepsilon = 1/\sqrt{n}$.

arXiv:1503.02868•Mar 10, 2015•5 citations
Boolean function monotonicity testing requires (almost) n1/2n^{1/2}n1/2 queries
We show that for any constant c>0c>0c>0, any (two-sided error) adaptive algorithm for testing monotonicity of Boolean functions must have query complexity Ω(n1/2−c)Ω(n^{1/2-c})Ω(n1/2−c). This improves the Ω~(n1/3)\tildeΩ(n^{1/3})Ω~(n1/3) lower bound of [CWX17] and almost matches the O~(n)\tilde{O}(\sqrt{n})O~(n​) upper bound of [KMS18].
The model of relative-error property testing of Boolean functions has been the subject of significant recent research effort [CDH+24][CPPS25a][CPPS25b] In this paper we consider the problem of relative-error testing an unknown and arbitrary f:{0,1}n→{0,1}f: \{0,1\}^n \to \{0,1\}f:{0,1}n→{0,1} for the property of being a unate function, i.e. a function that is either monotone non-increasing or monotone non-decreasing in each of the nnn input variables. Our first result is a one-sided non-adaptive algorithm for this problem that makes O~(log⁡(N)/ε)\tilde{O}(\log(N)/ε)O~(log(N)/ε) samples and queries, where N=∣f−1(1)∣N=|f^{-1}(1)|N=∣f−1(1)∣ is the number of satisfying assignments of the function that is being tested and the value of NNN is given as an input parameter to the algorithm. Building on this algorithm, we next give a one-sided adaptive algorithm for this problem that does not need to be given the value of NNN and with high probability makes O~(log⁡(N)/ε)\tilde{O}(\log(N)/ε)O~(log(N)/ε) samples and queries. We also give lower bounds for both adaptive and non-adaptive two-sided algorithms that are given the value of NNN up to a constant multiplicative factor. In the non-adaptive case, our lower bounds essentially match the complexity of the algorithm that we provide.
The Total Influence ( Average Sensitivity ) of a discrete function is one of its fundamental measures. We study the problem of approximating the total influence of a monotone Boolean function, which we denote by I [ f ]. We present a randomized algorithm that approximates the influence of such functions to within a multiplicative factor of (1 ± ε ) by performing O (√ n I [ f ] poly(1/ ε )) queries. We also prove a lower bound of Ω (√ n log n · I [ f ]) on the query complexity of any constant factor approximation algorithm for this problem (which holds for I [ f ]= Ω (1)), hence showing that our algorithm is almost optimal in terms of its dependence on n . For general functions, we give a lower bound of Ω ( n I [ f ]), which matches the complexity of a simple sampling algorithm.
We study the query complexity of Boolean functions f:{0,1}n→{0,1}f: \{0, 1\}^n \rightarrow \{0, 1\}f:{0,1}n→{0,1} in the noisy query model introduced by Feige, Raghavan, Peleg and Upfal [SICOMP 1994]. In this model, an algorithm can adaptively query the bits of an input vector, but each query result is independently flipped with constant probability p∈(0,1/2)p \in (0, 1/2)p∈(0,1/2); repeated queries are allowed. The noisy query complexity Np(f)\mathsf{N}_p(f)Np​(f) of a function fff is defined as the minimum expected number of queries needed to compute f(x)f(x)f(x) with error probability at most 1/31/31/3, for the worst case input xxx. We prove a general lower bound on Np(f)\mathsf{N}_p(f)Np​(f) based on degree statistics of certain subgraphs of the Boolean hypercube. This is the first general lower bound beyond those implied by the simple observation that Np(f)\mathsf{N}_p(f)Np​(f) is lower bounded by the randomized query complexity. We show that this recovers (up to a constant factor) most previously known lower bounds on the noisy query complexity of Boolean functions, providing a unified framework for understanding these results and simplifying the proofs in several cases. Furthermore, this resolves in the affirmative an open problem of Gu, Li and Xu [COLT 2025] that Np(f)=Ω(I(f)log⁡I(f))\mathsf{N}_p(f) = Ω(\mathsf{I}(f) \log \mathsf{I}(f))Np​(f)=Ω(I(f)logI(f)), where I(f)\mathsf{I}(f)I(f) denotes the total influence of fff. We also apply our general lower bound to obtain tight bounds on the noisy query complexity for several new functions.
In this note, we develop a bounded-error quantum algorithm that makes O~(n1/4ε−1/2)\tilde O(n^{1/4}\varepsilon^{-1/2})O~(n1/4ε−1/2) queries to a Boolean function fff, accepts a monotone function, and rejects a function that is ε\varepsilonε-far from being monotone. This gives a super-quadratic improvement compared to the best known randomized algorithm for all ε=o(1)\varepsilon = o(1)ε=o(1). The improvement is cubic when ε=1/n\varepsilon = 1/\sqrt{n}ε=1/n​.