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

Electronic colloquium on computational complexity

The Spectrum of Small DeMorgan Formulas.

Anat Ganor, Ilan Komargodski, Ran Raz

Published Jan 1, 2012• 4 citations
OpenAlex

Abstract

We show a connection between the deMorgan formula size of a Boolean function and the noise stability of the function. Using this connection, we show that the Fourier spectrum of any balanced Boolean function computed by a deMorgan formula of size s is concentrated on coefficients of degree up to O( √ s). These results have several applications that apply to any function f that can be computed by a deMorgan formula of size s. First, we get that f can be approximated (in L2-norm) with constant error by a polynomial of degree O( √ s). Second, we show an upper bound of O( √ s) on the average sensitivity of f . Our main result stems from a generalization of Khrapchenko’s bound [Khr71], that might be of independent interest, and some Fourier analysis on the Boolean cube. Previous works prove that any function f : {0, 1}n → {0, 1} that can be computed by a deMorgan formula of size s, can be approximated point-wise by a polynomial of degree O(s/2+o(1)) with constant point-wise error. We note that this result can be easily extended to have a polynomial of degree O(t ·s/2+o(1)) that approximates f with point-wise error 2−t, for any t > 0. This was shown in a long line of results in quantum complexity, including [BBC+01] and [FGG08, ACR+07, RS08, Rei09].

Related papers

Lower bounds of quantum black-box complexity and degree of approximation polynomials by influence of Boolean variables

Yaoyun Shi

We prove that, to compute a Boolean function $f$ on $N$ variables with error probability $ε$, any quantum black-box algorithm has to query at least $\frac{1 - 2\sqrtε}{2} ρ_f N = \frac{1 - 2\sqrtε}{2} \bar{S}_f$ times, where $ρ_f$ is the average influence of variables in $f$, and $\bar{S}_f$ is the average sensitivity. It's interesting to contrast this result with the known lower bound of $Ω(\sqrt{S_f})$, where $S_f$ is the sensitivity of $f$. This lower bound is tight for some functions. We also show for any polynomial $\tilde{f}$ that approximates $f$ with error probability $ε$, $deg(\tilde{f}) \ge 1/4 (1 - \frac{3 ε}{1 + ε})^2 ρ_f N$. This bound can be better than previous known lower bound of $Ω(\sqrt{BS_f})$ for some functions. Our technique may be of intest itself: we apply Fourier analysis to functions mapping $\{0, 1\}^N$ to unit vectors in a Hilbert space. From this viewpoint, the state of the quantum computer at step $t$ can be written as $\sum_{s\in \{0, 1\}^N, |s| \le t} \hatϕ_s (-1)^ {s \cdot x}$, which is handy for lower bound analysis.

arXiv:quant-ph/9904107•Apr 29, 1999•7 citations

Fourier Entropy Bounds via Approximations

Manaswi Paraashar, Nitin Saurabh

We establish upper bounds on the Shannon entropy $\mathbb H(\widehat f^{\,2})$ of the Fourier distribution of Boolean functions. We prove that $$ \mathbb H(\widehat f^{\,2}) =O\!\left(\log\bigl(1+\|\widehat f\|_{1,1/3}\bigr)\right), $$ where $\|\widehat f\|_{1,1/3}$ denotes the minimum spectral norm of a pointwise $1/3$-approximant to $f$. This implies $\mathbb H(\widehat f^{\,2})=O(\mathsf R^\oplus(f))$, where $\mathsf R^\oplus(f)$ is bounded-error randomized parity-query complexity. We also bound Fourier entropy by the smaller of the two one-sided average unambiguous parity-certificate complexities. More generally, for any exact representation of indicator of $f$ as $\sum_C w_C\mathbf1_C$, with nonnegative weights and affine subspaces $C$, we prove $$ \mathbb H(\widehat f^{\,2}) =O\!\left(\sum_C w_C\,2^{-k_C}k_C\right), \qquad k_C=\operatorname{codim}(C). $$ The quantity on the right is the average conical junta degree of the representation. These results strengthen earlier bounds of (Arunachalam et al. 2021) by extending approximation-based entropy estimates to Shannon entropy and allowing one-sided and overlapping exact representations. The proofs use an entropy bound from a sequence of increasingly accurate approximants of $f$ with \emph{small} spectral norm. Our techniques also find an application in quantum communication complexity, where it improves a lower bound for the bounded-error quantum communication complexity of XOR functions.

arXiv:2611.06451•Nov 4, 2026•0 citations

Restriction Trees for Sparsity and Applications

Arkadev Chattopadhyay, Yogesh Dahiya, Shachar Lovett

Exact and point-wise approximating representations of Boolean functions by real polynomials have been of great interest in the theory of computing. We focus on the study of sparsity of such representations. Our results include the following: First, we show that for every total Boolean function, its exact and approximate sparsity in the De Morgan basis are polynomially related to each other in the log scale, ignoring poly-log(n) factors. This answers an open question posed by Knop, Lovett, McGuire and Yuan (STOC 2021). It builds on and is analogous to the seminal result of Nisan and Szegedy (Computational Complexity 1994) who proved the same for degree and approximate degree. Second, we consider more powerful representations using generalized monomials, where each monomial is an indicator of a sub-cube. There are 3n such monomials, where n is the number of variables. We prove that even for these representations, the sparsity and approximate sparsity of total Boolean functions remain polynomially related to each other in the log scale, ignoring poly-log(n) factors. Third, we show that for every total Boolean function f, the log of its De Morgan sparsity characterizes up to polynomial loss and ignoring poly-log(n) factors, the quantum and classical 2-party bounded-error communication complexity of f ∘ EQ4, where EQ4 is Equality of two 2-bit strings, one held by Alice and the other by Bob. As a consequence, we show that bounded-error quantum protocols cannot exhibit super-polynomial cost advantage over their classical counterparts, for computing such functions.

ACM Symposium on Theory of Computing (STOC)•Jun 9, 2026•0 citations

Lower Bounds for the Approximate Degree of Block-Composed Functions

Justin Thaler

We describe a new hardness amplification result for point-wise approximation of Boolean functions by low-degree polynomials. Specifically, for any function f on N bits, define F(x_1,...,x_M) = OMB(f(x_1),...,f(x_M)) to be the function on M*N bits obtained by block-composing f with a function known as ODD-MAX-BIT. We show that, if f requires large degree to approximate to error 2/3 in a certain one-sided sense (captured by a complexity measure known as positive one-sided approximate degree), then F requires large degree to approximate even to error 1-2^{-M}. This generalizes a result of Beigel (Computational Complexity, 1994), who proved an identical result for the special case f=OR. Unlike related prior work, our result implies strong approximate degree lower bounds even for many functions F that have low threshold degree. Our proof is constructive: we exhibit a solution to the dual of an appropriate linear program capturing the approximate degree of any function. We describe several applications, including improved separations between the complexity classes P^{NP} and PP in both the query and communication complexity settings. Our separations improve on work of Beigel (1994) and Buhrman, Vereshchagin, and de Wolf (CCC, 2007).

Leibniz international proceedings in informatics•Jan 1, 2016•21 citations

A note on the sign degree of formulas

Troy Lee

Recent breakthroughs in quantum query complexity have shown that any formula of size n can be evaluated with O(sqrt(n)log(n)/log log(n)) many quantum queries in the bounded-error setting [FGG08, ACRSZ07, RS08b, Rei09]. In particular, this gives an upper bound on the approximate polynomial degree of formulas of the same magnitude, as approximate polynomial degree is a lower bound on quantum query complexity [BBCMW01]. These results essentially answer in the affirmative a conjecture of O'Donnell and Servedio [O'DS03] that the sign degree--the minimal degree of a polynomial that agrees in sign with a function on the Boolean cube--of every formula of size n is O(sqrt(n)). In this note, we show that sign degree is super-multiplicative under function composition. Combining this result with the above mentioned upper bounds on the quantum query complexity of formulas allows the removal of logarithmic factors to show that the sign degree of every size n formula is at most sqrt(n).

arXiv:0909.4607•Sep 25, 2009•38 citations

THE QUANTUM ADVERSARY METHOD AND CLASSICAL FORMULA SIZE LOWER BOUNDS

Sophie Laplante, Troy Lee, Márió Szegedy

We introduce two new complexity measures for Boolean functions, which we name sumPI and maxPI . The quantity sumPI has been emerging through a line of research on quantum query complexity lower bounds via the so-called quantum adversary method (Ambainis 2002, 2003; Barnum et al. 2003; Laplante & Magniez 2004; Zhang 2005), culminating in Špalek & Szegedy (2005) with the realization that these many different formulations are in fact equivalent. Given that sumPI turns out to be such a robust invariant of a function, we begin to investigate this quantity in its own right and see that it also has applications to classical complexity theory. As a surprising application we show that sumPI 2(f) is a lower bound on the formula size, and even, up to a constant multiplicative factor, the probabilistic formula size of f. We show that several formula size lower bounds in the literature, specifically Khrapchenko and its extensions (Khrapchenko 1971; Koutsoupias 1993), including a key lemma of Håstad (1998), are in fact special cases of our method. The second quantity we introduce, maxPI (f), is always at least as large as sumPI(f) , and is derived from sumPI in such a way that maxPI 2(f) remains a lower bound on formula size. Our main result is proven via a combinatorial lemma which relates the square of the spectral norm of a matrix to the squares of the spectral norms of its submatrices. The generality of this lemma implies that our methods can also be used to lower-bound the communication complexity of relations, and a related combinatorial quantity, the rectangle partition number. To exhibit the strengths and weaknesses of our methods, we look at the sumPI and maxPI complexity of a few examples, including the recursive majority of three function, a function defined by Ambainis (2003), and the collision problem.

arXiv:quant-ph/0501057•Computational Complexity•Jun 1, 2006•63 citations
We show a connection between the deMorgan formula size of a Boolean function and the noise stability of the function. Using this connection, we show that the Fourier spectrum of any balanced Boolean function computed by a deMorgan formula of size s is concentrated on coefficients of degree up to O( √ s). These results have several applications that apply to any function f that can be computed by a deMorgan formula of size s. First, we get that f can be approximated (in L2-norm) with constant error by a polynomial of degree O( √ s). Second, we show an upper bound of O( √ s) on the average sensitivity of f . Our main result stems from a generalization of Khrapchenko’s bound [Khr71], that might be of independent interest, and some Fourier analysis on the Boolean cube. Previous works prove that any function f : {0, 1}n → {0, 1} that can be computed by a deMorgan formula of size s, can be approximated point-wise by a polynomial of degree O(s/2+o(1)) with constant point-wise error. We note that this result can be easily extended to have a polynomial of degree O(t ·s/2+o(1)) that approximates f with point-wise error 2−t, for any t > 0. This was shown in a long line of results in quantum complexity, including [BBC+01] and [FGG08, ACR+07, RS08, Rei09].
We prove that, to compute a Boolean function fff on NNN variables with error probability εεε, any quantum black-box algorithm has to query at least 1−2ε2ρfN=1−2ε2Sˉf\frac{1 - 2\sqrtε}{2} ρ_f N = \frac{1 - 2\sqrtε}{2} \bar{S}_f21−2ε​​ρf​N=21−2ε​​Sˉf​ times, where ρfρ_fρf​ is the average influence of variables in fff, and Sˉf\bar{S}_fSˉf​ is the average sensitivity. It's interesting to contrast this result with the known lower bound of Ω(Sf)Ω(\sqrt{S_f})Ω(Sf​​), where SfS_fSf​ is the sensitivity of fff. This lower bound is tight for some functions. We also show for any polynomial f~\tilde{f}f~​ that approximates fff with error probability εεε, deg(f~)≥1/4(1−3ε1+ε)2ρfNdeg(\tilde{f}) \ge 1/4 (1 - \frac{3 ε}{1 + ε})^2 ρ_f Ndeg(f~​)≥1/4(1−1+ε3ε​)2ρf​N. This bound can be better than previous known lower bound of Ω(BSf)Ω(\sqrt{BS_f})Ω(BSf​​) for some functions. Our technique may be of intest itself: we apply Fourier analysis to functions mapping {0,1}N\{0, 1\}^N{0,1}N to unit vectors in a Hilbert space. From this viewpoint, the state of the quantum computer at step ttt can be written as ∑s∈{0,1}N,∣s∣≤tϕ^s(−1)s⋅x\sum_{s\in \{0, 1\}^N, |s| \le t} \hatϕ_s (-1)^ {s \cdot x}∑s∈{0,1}N,∣s∣≤t​ϕ^​s​(−1)s⋅x, which is handy for lower bound analysis.
We establish upper bounds on the Shannon entropy H(f^ 2)\mathbb H(\widehat f^{\,2})H(f​2) of the Fourier distribution of Boolean functions. We prove that H(f^ 2)=O ⁣(log⁡(1+∥f^∥1,1/3)), \mathbb H(\widehat f^{\,2}) =O\!\left(\log\bigl(1+\|\widehat f\|_{1,1/3}\bigr)\right), H(f​2)=O(log(1+∥f​∥1,1/3​)), where ∥f^∥1,1/3\|\widehat f\|_{1,1/3}∥f​∥1,1/3​ denotes the minimum spectral norm of a pointwise 1/31/31/3-approximant to fff. This implies H(f^ 2)=O(R⊕(f))\mathbb H(\widehat f^{\,2})=O(\mathsf R^\oplus(f))H(f​2)=O(R⊕(f)), where R⊕(f)\mathsf R^\oplus(f)R⊕(f) is bounded-error randomized parity-query complexity. We also bound Fourier entropy by the smaller of the two one-sided average unambiguous parity-certificate complexities. More generally, for any exact representation of indicator of fff as ∑CwC1C\sum_C w_C\mathbf1_C∑C​wC​1C​, with nonnegative weights and affine subspaces CCC, we prove H(f^ 2)=O ⁣(∑CwC 2−kCkC),kC=codim⁡(C). \mathbb H(\widehat f^{\,2}) =O\!\left(\sum_C w_C\,2^{-k_C}k_C\right), \qquad k_C=\operatorname{codim}(C). H(f​2)=O(∑C​wC​2−kC​kC​),kC​=codim(C). The quantity on the right is the average conical junta degree of the representation. These results strengthen earlier bounds of (Arunachalam et al. 2021) by extending approximation-based entropy estimates to Shannon entropy and allowing one-sided and overlapping exact representations. The proofs use an entropy bound from a sequence of increasingly accurate approximants of fff with \emph{small} spectral norm. Our techniques also find an application in quantum communication complexity, where it improves a lower bound for the bounded-error quantum communication complexity of XOR functions.
Exact and point-wise approximating representations of Boolean functions by real polynomials have been of great interest in the theory of computing. We focus on the study of sparsity of such representations. Our results include the following: First, we show that for every total Boolean function, its exact and approximate sparsity in the De Morgan basis are polynomially related to each other in the log scale, ignoring poly-log(n) factors. This answers an open question posed by Knop, Lovett, McGuire and Yuan (STOC 2021). It builds on and is analogous to the seminal result of Nisan and Szegedy (Computational Complexity 1994) who proved the same for degree and approximate degree. Second, we consider more powerful representations using generalized monomials, where each monomial is an indicator of a sub-cube. There are 3n such monomials, where n is the number of variables. We prove that even for these representations, the sparsity and approximate sparsity of total Boolean functions remain polynomially related to each other in the log scale, ignoring poly-log(n) factors. Third, we show that for every total Boolean function f, the log of its De Morgan sparsity characterizes up to polynomial loss and ignoring poly-log(n) factors, the quantum and classical 2-party bounded-error communication complexity of f ∘ EQ4, where EQ4 is Equality of two 2-bit strings, one held by Alice and the other by Bob. As a consequence, we show that bounded-error quantum protocols cannot exhibit super-polynomial cost advantage over their classical counterparts, for computing such functions.
We describe a new hardness amplification result for point-wise approximation of Boolean functions by low-degree polynomials. Specifically, for any function f on N bits, define F(x_1,...,x_M) = OMB(f(x_1),...,f(x_M)) to be the function on M*N bits obtained by block-composing f with a function known as ODD-MAX-BIT. We show that, if f requires large degree to approximate to error 2/3 in a certain one-sided sense (captured by a complexity measure known as positive one-sided approximate degree), then F requires large degree to approximate even to error 1-2^{-M}. This generalizes a result of Beigel (Computational Complexity, 1994), who proved an identical result for the special case f=OR. Unlike related prior work, our result implies strong approximate degree lower bounds even for many functions F that have low threshold degree. Our proof is constructive: we exhibit a solution to the dual of an appropriate linear program capturing the approximate degree of any function. We describe several applications, including improved separations between the complexity classes P^{NP} and PP in both the query and communication complexity settings. Our separations improve on work of Beigel (1994) and Buhrman, Vereshchagin, and de Wolf (CCC, 2007).
Recent breakthroughs in quantum query complexity have shown that any formula of size n can be evaluated with O(sqrt(n)log(n)/log log(n)) many quantum queries in the bounded-error setting [FGG08, ACRSZ07, RS08b, Rei09]. In particular, this gives an upper bound on the approximate polynomial degree of formulas of the same magnitude, as approximate polynomial degree is a lower bound on quantum query complexity [BBCMW01]. These results essentially answer in the affirmative a conjecture of O'Donnell and Servedio [O'DS03] that the sign degree--the minimal degree of a polynomial that agrees in sign with a function on the Boolean cube--of every formula of size n is O(sqrt(n)). In this note, we show that sign degree is super-multiplicative under function composition. Combining this result with the above mentioned upper bounds on the quantum query complexity of formulas allows the removal of logarithmic factors to show that the sign degree of every size n formula is at most sqrt(n).
We introduce two new complexity measures for Boolean functions, which we name sumPI and maxPI . The quantity sumPI has been emerging through a line of research on quantum query complexity lower bounds via the so-called quantum adversary method (Ambainis 2002, 2003; Barnum et al. 2003; Laplante & Magniez 2004; Zhang 2005), culminating in Špalek & Szegedy (2005) with the realization that these many different formulations are in fact equivalent. Given that sumPI turns out to be such a robust invariant of a function, we begin to investigate this quantity in its own right and see that it also has applications to classical complexity theory. As a surprising application we show that sumPI 2(f) is a lower bound on the formula size, and even, up to a constant multiplicative factor, the probabilistic formula size of f. We show that several formula size lower bounds in the literature, specifically Khrapchenko and its extensions (Khrapchenko 1971; Koutsoupias 1993), including a key lemma of Håstad (1998), are in fact special cases of our method. The second quantity we introduce, maxPI (f), is always at least as large as sumPI(f) , and is derived from sumPI in such a way that maxPI 2(f) remains a lower bound on formula size. Our main result is proven via a combinatorial lemma which relates the square of the spectral norm of a matrix to the squares of the spectral norms of its submatrices. The generality of this lemma implies that our methods can also be used to lower-bound the communication complexity of relations, and a related combinatorial quantity, the rectangle partition number. To exhibit the strengths and weaknesses of our methods, we look at the sumPI and maxPI complexity of a few examples, including the recursive majority of three function, a function defined by Ambainis (2003), and the collision problem.