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:2512.13566

A Distance Amplification Lemma for Monotonicity

Dor Minzer

Published Dec 15, 2025• 0 citations
arXivHTMLPDF

Abstract

We show a procedure that, given oracle access to a function $f\colon \{0,1\}^n\to\{0,1\}$, produces oracle access to a function $f'\colon \{0,1\}^{n'}\to\{0,1\}$ such that if $f$ is monotone, then $f'$ is monotone, and if $f$ is $\varepsilon$-far from monotone, then $f'$ is $Ω(1)$-far from monotone. Moreover, $n' \leq n 2^{O(1/\varepsilon)}$ and each oracle query to $f'$ can be answered by making $2^{O(1/\varepsilon)}$ oracle queries to $f$. Our lemma is motivated by a recent result of [Chen, Chen, Cui, Pires, Stockwell, arXiv:2511.04558], who showed that for all $c>0$ there exists $\varepsilon_c>0$, such that any (even two-sided, adaptive) algorithm distinguishing between monotone functions and $\varepsilon_c$-far from monotone functions, requires $Ω(n^{1/2-c})$ queries. Combining our lemma with their result implies a similar result, except that the distance from monotonicity is an absolute constant $\varepsilon>0$, and the lower bound is $Ω(n^{1/2-o(1)})$ queries.

DOI
10.48550/arxiv.2512.13566

Related papers

A o(n) monotonicity tester for boolean functions over the hypercube

Deeparnab Chakrabarty, Comandur Seshadhri

Given oracle access to a Boolean function f:{0,1}n -> {0,1}, we design a randomized tester that takes as input a parameter ε>0, and outputs Yes if the function is monotonically non-increasing, and outputs No with probability >2/3, if the function is ε-far from being monotone, that is, f needs to be modified at ε-fraction of the points to make it monotone. Our non-adaptive, one-sided tester makes ~O(n5/6ε-5/3) queries to the oracle.

ACM Symposium on Theory of Computing (STOC)•May 28, 2013•30 citations

Boolean 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].

arXiv:2511.04558•Nov 6, 2025•0 citations

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•42 citations

Approximating the Noise Sensitivity of a Monotone Boolean Function

Ronitt Rubinfeld, Arsen Vasilyan

The noise sensitivity of a Boolean function f: {0,1}^n - > {0,1} is one of its fundamental properties. For noise parameter delta, the noise sensitivity is denoted as NS_{delta}[f]. This quantity is defined as follows: First, pick x = (x_1,...,x_n) uniformly at random from {0,1}^n, then pick z by flipping each x_i independently with probability delta. NS_{delta}[f] is defined to equal Pr [f(x) != f(z)]. Much of the existing literature on noise sensitivity explores the following two directions: (1) Showing that functions with low noise-sensitivity are structured in certain ways. (2) Mathematically showing that certain classes of functions have low noise sensitivity. Combined, these two research directions show that certain classes of functions have low noise sensitivity and therefore have useful structure. The fundamental importance of noise sensitivity, together with this wealth of structural results, motivates the algorithmic question of approximating NS_{delta}[f] given an oracle access to the function f. We show that the standard sampling approach is essentially optimal for general Boolean functions. Therefore, we focus on estimating the noise sensitivity of monotone functions, which form an important subclass of Boolean functions, since many functions of interest are either monotone or can be simply transformed into a monotone function (for example the class of unate functions consists of all the functions that can be made monotone by reorienting some of their coordinates [O'Donnell, 2014]). Specifically, we study the algorithmic problem of approximating NS_{delta}[f] for monotone f, given the promise that NS_{delta}[f] >= 1/n^{C} for constant C, and for delta in the range 1/n <= delta <= 1/2. For such f and delta, we give a randomized algorithm performing O((min(1,sqrt{n} delta log^{1.5} n))/(NS_{delta}[f]) poly (1/epsilon)) queries and approximating NS_{delta}[f] to within a multiplicative factor of (1 +/- epsilon). Given the same constraints on f and delta, we also prove a lower bound of Omega((min(1,sqrt{n} delta))/(NS_{delta}[f] * n^{xi})) on the query complexity of any algorithm that approximates NS_{delta}[f] to within any constant factor, where xi can be any positive constant. Thus, our algorithm’s query complexity is close to optimal in terms of its dependence on n. We introduce a novel descending-ascending view of noise sensitivity, and use it as a central tool for the analysis of our algorithm. To prove lower bounds on query complexity, we develop a technique that reduces computational questions about query complexity to combinatorial questions about the existence of "thin" functions with certain properties. The existence of such "thin" functions is proved using the probabilistic method. These techniques also yield new lower bounds on the query complexity of approximating other fundamental properties of Boolean functions: the total influence and the bias.

arXiv:1904.06745•Leibniz international proceedings in informatics•Jan 1, 2019•0 citations

The Quantumly Fast and the Classically Forrious

Clément L. Canonne, Kenny Chen, Julián Mestre

We study the extremal Forrelation problem, where, provided with oracle access to Boolean functions $f$ and $g$ promised to satisfy either $\operatorname{forr}(f,g)=1$ or $\operatorname{forr}(f,g)=-1$, one must determine (with high probability) which of the two cases holds while performing as few oracle queries as possible. It is well known that this problem can be solved with one quantum query; yet, Girish and Servedio (ITCS 2026) recently showed this problem requires $\widetildeΩ(2^{n/4})$ classical queries, and conjectured the optimal bound to be $\widetildeΘ(2^{n/2})$. By generalizing their construction, we build on their result and prove a non-adaptive lower bound of $Ω(2^{(1/2- o(1))n})$, which matches the conjectured lower bound up to a vanishing constant in the exponent.

arXiv:2602.07503•Feb 7, 2026•0 citations

Quantum Advantage in Tolerant Junta Testing

Avishay Tal, Weiqiang Yuan

We establish the first super-polynomial quantum advantage for the tolerant junta testing problem in the adaptive setting. Specifically, we show that within a certain parameter regime, tolerant $k$-junta testing with high precision can be solved using $\mathrm{poly}(k)$ quantum queries, whereas any classical algorithm requires at least $k^{Ω(\log k)}$ queries. The problem of tolerant $k$-junta testing is as follows: given parameters $(k, ε_1, ε_2)$, with $0\le ε_1<ε_2 \le 1/2$, and black-box access to a Boolean function $f$ (defined on $n$ variables), distinguish whether $f$ is $ε_1$-close to some $k$-junta or $ε_2$-far from every $k$-junta. We show the quantum advantage for a range of parameters close to $1/2$, for example, $ε_1 = 1/2-1/k$ and $ε_2 = 1/2-1/(2k^2)$. The (non-adaptive) quantum tester we use was given by a recent work of Bao, Liu, Yao, Ye, and Zhang (SOSA 2026). We slightly adapt their analysis to show that it holds in the above parameter regime. On the other hand, our classical lower bound requires substantial new ideas. Inspired by the lower bound techniques of Chen and Patel (FOCS 2023), we introduce a new hard distribution of ``yes'' instances (i.e., instances with distance at most $ε_1$ to $k$-juntas) that is based on planting an ``approximate-junta'' as follows: we randomly pick $k$ out of $n$ coordinates, and for each fixing of the $k$ coordinates, the $2^{n-k}$ values in the restricted subcube are drawn randomly except for the set of points in an error-correcting code on which we place the same random bit. We show that this distribution is much closer to $k$-juntas than the uniform distribution, but on the other hand, they are indistinguishable with respect to any classical algorithm making $k^{o(\log k)}$ queries.

cs.CCCross-listedarXiv:2606.23194•Jun 23, 2026•0 citations
We show a procedure that, given oracle access to a function f ⁣:{0,1}n→{0,1}f\colon \{0,1\}^n\to\{0,1\}f:{0,1}n→{0,1}, produces oracle access to a function f′ ⁣:{0,1}n′→{0,1}f'\colon \{0,1\}^{n'}\to\{0,1\}f′:{0,1}n′→{0,1} such that if fff is monotone, then f′f'f′ is monotone, and if fff is ε\varepsilonε-far from monotone, then f′f'f′ is Ω(1)Ω(1)Ω(1)-far from monotone. Moreover, n′≤n2O(1/ε)n' \leq n 2^{O(1/\varepsilon)}n′≤n2O(1/ε) and each oracle query to f′f'f′ can be answered by making 2O(1/ε)2^{O(1/\varepsilon)}2O(1/ε) oracle queries to fff. Our lemma is motivated by a recent result of [Chen, Chen, Cui, Pires, Stockwell, arXiv:2511.04558], who showed that for all c>0c>0c>0 there exists εc>0\varepsilon_c>0εc​>0, such that any (even two-sided, adaptive) algorithm distinguishing between monotone functions and εc\varepsilon_cεc​-far from monotone functions, requires Ω(n1/2−c)Ω(n^{1/2-c})Ω(n1/2−c) queries. Combining our lemma with their result implies a similar result, except that the distance from monotonicity is an absolute constant ε>0\varepsilon>0ε>0, and the lower bound is Ω(n1/2−o(1))Ω(n^{1/2-o(1)})Ω(n1/2−o(1)) queries.
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 noise sensitivity of a Boolean function f: {0,1}^n - > {0,1} is one of its fundamental properties. For noise parameter delta, the noise sensitivity is denoted as NS_{delta}[f]. This quantity is defined as follows: First, pick x = (x_1,...,x_n) uniformly at random from {0,1}^n, then pick z by flipping each x_i independently with probability delta. NS_{delta}[f] is defined to equal Pr [f(x) != f(z)]. Much of the existing literature on noise sensitivity explores the following two directions: (1) Showing that functions with low noise-sensitivity are structured in certain ways. (2) Mathematically showing that certain classes of functions have low noise sensitivity. Combined, these two research directions show that certain classes of functions have low noise sensitivity and therefore have useful structure. The fundamental importance of noise sensitivity, together with this wealth of structural results, motivates the algorithmic question of approximating NS_{delta}[f] given an oracle access to the function f. We show that the standard sampling approach is essentially optimal for general Boolean functions. Therefore, we focus on estimating the noise sensitivity of monotone functions, which form an important subclass of Boolean functions, since many functions of interest are either monotone or can be simply transformed into a monotone function (for example the class of unate functions consists of all the functions that can be made monotone by reorienting some of their coordinates [O'Donnell, 2014]). Specifically, we study the algorithmic problem of approximating NS_{delta}[f] for monotone f, given the promise that NS_{delta}[f] >= 1/n^{C} for constant C, and for delta in the range 1/n <= delta <= 1/2. For such f and delta, we give a randomized algorithm performing O((min(1,sqrt{n} delta log^{1.5} n))/(NS_{delta}[f]) poly (1/epsilon)) queries and approximating NS_{delta}[f] to within a multiplicative factor of (1 +/- epsilon). Given the same constraints on f and delta, we also prove a lower bound of Omega((min(1,sqrt{n} delta))/(NS_{delta}[f] * n^{xi})) on the query complexity of any algorithm that approximates NS_{delta}[f] to within any constant factor, where xi can be any positive constant. Thus, our algorithm’s query complexity is close to optimal in terms of its dependence on n. We introduce a novel descending-ascending view of noise sensitivity, and use it as a central tool for the analysis of our algorithm. To prove lower bounds on query complexity, we develop a technique that reduces computational questions about query complexity to combinatorial questions about the existence of "thin" functions with certain properties. The existence of such "thin" functions is proved using the probabilistic method. These techniques also yield new lower bounds on the query complexity of approximating other fundamental properties of Boolean functions: the total influence and the bias.
We study the extremal Forrelation problem, where, provided with oracle access to Boolean functions fff and ggg promised to satisfy either forr⁡(f,g)=1\operatorname{forr}(f,g)=1forr(f,g)=1 or forr⁡(f,g)=−1\operatorname{forr}(f,g)=-1forr(f,g)=−1, one must determine (with high probability) which of the two cases holds while performing as few oracle queries as possible. It is well known that this problem can be solved with one quantum query; yet, Girish and Servedio (ITCS 2026) recently showed this problem requires Ω~(2n/4)\widetildeΩ(2^{n/4})Ω(2n/4) classical queries, and conjectured the optimal bound to be Θ~(2n/2)\widetildeΘ(2^{n/2})Θ(2n/2). By generalizing their construction, we build on their result and prove a non-adaptive lower bound of Ω(2(1/2−o(1))n)Ω(2^{(1/2- o(1))n})Ω(2(1/2−o(1))n), which matches the conjectured lower bound up to a vanishing constant in the exponent.
We establish the first super-polynomial quantum advantage for the tolerant junta testing problem in the adaptive setting. Specifically, we show that within a certain parameter regime, tolerant kkk-junta testing with high precision can be solved using poly(k)\mathrm{poly}(k)poly(k) quantum queries, whereas any classical algorithm requires at least kΩ(log⁡k)k^{Ω(\log k)}kΩ(logk) queries. The problem of tolerant kkk-junta testing is as follows: given parameters (k,ε1,ε2)(k, ε_1, ε_2)(k,ε1​,ε2​), with 0≤ε1<ε2≤1/20\le ε_1<ε_2 \le 1/20≤ε1​<ε2​≤1/2, and black-box access to a Boolean function fff (defined on nnn variables), distinguish whether fff is ε1ε_1ε1​-close to some kkk-junta or ε2ε_2ε2​-far from every kkk-junta. We show the quantum advantage for a range of parameters close to 1/21/21/2, for example, ε1=1/2−1/kε_1 = 1/2-1/kε1​=1/2−1/k and ε2=1/2−1/(2k2)ε_2 = 1/2-1/(2k^2)ε2​=1/2−1/(2k2). The (non-adaptive) quantum tester we use was given by a recent work of Bao, Liu, Yao, Ye, and Zhang (SOSA 2026). We slightly adapt their analysis to show that it holds in the above parameter regime. On the other hand, our classical lower bound requires substantial new ideas. Inspired by the lower bound techniques of Chen and Patel (FOCS 2023), we introduce a new hard distribution of ``yes'' instances (i.e., instances with distance at most ε1ε_1ε1​ to kkk-juntas) that is based on planting an ``approximate-junta'' as follows: we randomly pick kkk out of nnn coordinates, and for each fixing of the kkk coordinates, the 2n−k2^{n-k}2n−k values in the restricted subcube are drawn randomly except for the set of points in an error-correcting code on which we place the same random bit. We show that this distribution is much closer to kkk-juntas than the uniform distribution, but on the other hand, they are indistinguishable with respect to any classical algorithm making ko(log⁡k)k^{o(\log k)}ko(logk) queries.