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

Algorithmica

A Lower Bound on the Trace Norm of Boolean Matrices and its Applications

Tsun-Ming Cheung, Hamed Hatami, Kaave Hosseini, Aleksandar Nikolov, Toniann Pitassi, Morgan Shirley

Published Jun 8, 2026• 4 citations
Publisher

Abstract

We present a simple method based on a variant of Hölder’s inequality to lower-bound the trace norm of Boolean matrices. As the main result, we obtain an exponential separation between the randomized decision tree depth and the spectral norm (i.e. the Fourier $$L_1$$ -norm) of a Boolean function. This answers an open question of Cheung, Hatami, Hosseini, and Shirley (CCC 2023). As immediate consequences, we obtain the following results.

DOI
10.1007/s00453-026-01396-2

Related papers

Lower bounds for noisy Boolean decision trees

William Evans, Nicholas J. Pippenger

We present a new method for deriving lower bounds to the expected number of queries made by noisy decision trees computing Boolean functions. The new method has the feature that expectations are taken with respect to a uniformly distributed random input, as well as with respect to the random noise, thus yielding stronger lower bounds. It also applies to many more functions than do previous results. The method yields a simple proof of the result (previously established by Reischuck and Schmeltz) that almost all Boolean functions of n arguments require Ω(n log n) queries and strengthens this bound from the worst-case over inputs to the average over inputs. The method also yields bounds for specific Boolean functions in terms of their spectra (their Fourier transforms). The simplest instance of this spectral bound yields the result (previously established by Feige, Peleg, Raghavan and Upfal) that the parity function of n arguments requires Ω(n log n) queries, and again strengthens this bound from the worst-case over inputs to the average over inputs. In its full generality, the spectral bound applies to the "highly resilient" functions introduced by Chor, Friedman, Goldreigh, Hastad, Rudich and Smolensky, and it yields non-linear lower bounds whenever the resiliency is asymptotic to the number of arguments.

ACM Symposium on Theory of Computing (STOC)•Jan 1, 1996•87 citations

Average-Case Lower Bounds for Noisy Boolean Decision Trees

William Evans, Nicholas J. Pippenger

We present a new method for deriving lower bounds to the expected number of queries made by noisy decision trees computing Boolean functions. The new method has the feature that expectations are taken with respect to a uniformly distributed random input, as well as with respect to the random noise, thus yielding stronger lower bounds. It also applies to many more functions than do previous results. The method yields a simple proof of the result (previously established by Reischuk and Schmeltz) that almost all Boolean functions of n arguments require $\Me(n \log n)$ queries, and strengthens this bound from the worst-case over inputs to the average over inputs. The method also yields bounds for specific Boolean functions in terms of their spectra (their Fourier transforms). The simplest instance of this spectral bound yields the result (previously established by Feige, Peleg, Raghavan, and Upfal) that the parity function of n arguments requires $\Me(n \log n)$ queries and again strengthens this bound from the worst-case over inputs to the average over inputs. In its full generality, the spectral bound applies to the "highly resilient" functions introduced by Chor, Friedman, Goldreich, Hastad, Rudich, and Smolensky, and it yields nonlinear lower bounds whenever the resiliency is asymptotic to the number of arguments.

SIAM Journal on Computing•Jan 1, 1998•19 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

Fourier Growth of Parity Decision Trees.

Uma Girish, Avishay Tal, Kewen Wu

We prove that for every parity decision tree of depth $d$ on $n$ variables, the sum of absolute values of Fourier coefficients at level $\ell$ is at most $d^{\ell/2} \cdot O(\ell \cdot \log(n))^\ell$. Our result is nearly tight for small values of $\ell$ and extends a previous Fourier bound for standard decision trees by Sherstov, Storozhenko, and Wu (STOC, 2021). As an application of our Fourier bounds, using the results of Bansal and Sinha (STOC, 2021), we show that the $k$-fold Forrelation problem has (randomized) parity decision tree complexity $\tilde{\Omega}\left(n^{1-1/k}\right)$, while having quantum query complexity $\lceil k/2\rceil$. Our proof follows a random-walk approach, analyzing the contribution of a random path in the decision tree to the level-$\ell$ Fourier expression. To carry the argument, we apply a careful cleanup procedure to the parity decision tree, ensuring that the value of the random walk is bounded with high probability. We observe that step sizes for the level-$\ell$ walks can be computed by the intermediate values of level $\le \ell-1$ walks, which calls for an inductive argument. Our approach differs from previous proofs of Tal (FOCS, 2020) and Sherstov, Storozhenko, and Wu (STOC, 2021) that relied on decompositions of the tree. In particular, for the special case of standard decision trees we view our proof as slightly simpler and more intuitive. In addition, we prove a similar bound for noisy decision trees of cost at most $d$ -- a model that was recently introduced by Ben-David and Blais (FOCS, 2020).

Electronic colloquium on computational complexity•Jan 1, 2021•0 citations

The pattern matrix method for lower bounds on quantum communication

Alexander A. Sherstov

In a breakthrough result, Razborov (2003) gave optimal lower bounds on the communication complexity of every function f of the form f(x,y)=D(|x AND y|) for some D:{0,1,...,n}->{0,1}, in the bounded-error quantum model with and without prior entanglement. This was proved by the multidimensional discrepancy method. We give an entirely different proof of Razborov's result, using the original, one-dimensional discrepancy method. This refutes the commonly held intuition (Razborov 2003) that the original discrepancy method fails for functions such as DISJOINTNESS. More importantly, our communication lower bounds hold for a much broader class of functions for which no methods were available. Namely, fix an arbitrary function f:{0,1}n/4->{0,1} and let A be the Boolean matrix whose columns are each an application of f to some subset of the variables x1,x2,...,xn. We prove that the communication complexity of A in the bounded-error quantum model with and without prior entanglement is Omega(d), where d is the approximate degree of f. From this result, Razborov's lower bounds follow easily. Our result also establishes a large new class of total Boolean functions whose quantum communication complexity (regardless of prior entanglement) is at best polynomially smaller than their classical complexity. Our proof method is a novel combination of two ingredients. The first is a certain equivalence of approximation and orthogonality in Euclidean n-space, which follows by linear-programming duality. The second is a new construction of suitably structured matrices with low spectral norm, the pattern matrices, which we realize using matrix analysis and the Fourier transform over (Z2)n. The method of this paper has recently inspired important progress in multiparty communication complexity.

ACM Symposium on Theory of Computing (STOC)•May 17, 2008•77 citations

The Spectrum of Small DeMorgan Formulas.

Anat Ganor, Ilan Komargodski, Ran Raz

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

Electronic colloquium on computational complexity•Jan 1, 2012•4 citations
We present a simple method based on a variant of Hölder’s inequality to lower-bound the trace norm of Boolean matrices. As the main result, we obtain an exponential separation between the randomized decision tree depth and the spectral norm (i.e. the Fourier L1L_1L1​ -norm) of a Boolean function. This answers an open question of Cheung, Hatami, Hosseini, and Shirley (CCC 2023). As immediate consequences, we obtain the following results.
We present a new method for deriving lower bounds to the expected number of queries made by noisy decision trees computing Boolean functions. The new method has the feature that expectations are taken with respect to a uniformly distributed random input, as well as with respect to the random noise, thus yielding stronger lower bounds. It also applies to many more functions than do previous results. The method yields a simple proof of the result (previously established by Reischuck and Schmeltz) that almost all Boolean functions of n arguments require Ω(n log n) queries and strengthens this bound from the worst-case over inputs to the average over inputs. The method also yields bounds for specific Boolean functions in terms of their spectra (their Fourier transforms). The simplest instance of this spectral bound yields the result (previously established by Feige, Peleg, Raghavan and Upfal) that the parity function of n arguments requires Ω(n log n) queries, and again strengthens this bound from the worst-case over inputs to the average over inputs. In its full generality, the spectral bound applies to the "highly resilient" functions introduced by Chor, Friedman, Goldreigh, Hastad, Rudich and Smolensky, and it yields non-linear lower bounds whenever the resiliency is asymptotic to the number of arguments.
We present a new method for deriving lower bounds to the expected number of queries made by noisy decision trees computing Boolean functions. The new method has the feature that expectations are taken with respect to a uniformly distributed random input, as well as with respect to the random noise, thus yielding stronger lower bounds. It also applies to many more functions than do previous results. The method yields a simple proof of the result (previously established by Reischuk and Schmeltz) that almost all Boolean functions of n arguments require $\Me(n \log n)$ queries, and strengthens this bound from the worst-case over inputs to the average over inputs. The method also yields bounds for specific Boolean functions in terms of their spectra (their Fourier transforms). The simplest instance of this spectral bound yields the result (previously established by Feige, Peleg, Raghavan, and Upfal) that the parity function of n arguments requires $\Me(n \log n)$ queries and again strengthens this bound from the worst-case over inputs to the average over inputs. In its full generality, the spectral bound applies to the "highly resilient" functions introduced by Chor, Friedman, Goldreich, Hastad, Rudich, and Smolensky, and it yields nonlinear lower bounds whenever the resiliency is asymptotic to the number of arguments.
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.
We prove that for every parity decision tree of depth ddd on nnn variables, the sum of absolute values of Fourier coefficients at level ℓ\ellℓ is at most dℓ/2⋅O(ℓ⋅log⁡(n))ℓd^{\ell/2} \cdot O(\ell \cdot \log(n))^\elldℓ/2⋅O(ℓ⋅log(n))ℓ. Our result is nearly tight for small values of ℓ\ellℓ and extends a previous Fourier bound for standard decision trees by Sherstov, Storozhenko, and Wu (STOC, 2021). As an application of our Fourier bounds, using the results of Bansal and Sinha (STOC, 2021), we show that the kkk-fold Forrelation problem has (randomized) parity decision tree complexity Ω~(n1−1/k)\tilde{\Omega}\left(n^{1-1/k}\right)Ω~(n1−1/k), while having quantum query complexity ⌈k/2⌉\lceil k/2\rceil⌈k/2⌉. Our proof follows a random-walk approach, analyzing the contribution of a random path in the decision tree to the level-ℓ\ellℓ Fourier expression. To carry the argument, we apply a careful cleanup procedure to the parity decision tree, ensuring that the value of the random walk is bounded with high probability. We observe that step sizes for the level-ℓ\ellℓ walks can be computed by the intermediate values of level ≤ℓ−1\le \ell-1≤ℓ−1 walks, which calls for an inductive argument. Our approach differs from previous proofs of Tal (FOCS, 2020) and Sherstov, Storozhenko, and Wu (STOC, 2021) that relied on decompositions of the tree. In particular, for the special case of standard decision trees we view our proof as slightly simpler and more intuitive. In addition, we prove a similar bound for noisy decision trees of cost at most ddd -- a model that was recently introduced by Ben-David and Blais (FOCS, 2020).
In a breakthrough result, Razborov (2003) gave optimal lower bounds on the communication complexity of every function f of the form f(x,y)=D(|x AND y|) for some D:{0,1,...,n}->{0,1}, in the bounded-error quantum model with and without prior entanglement. This was proved by the multidimensional discrepancy method. We give an entirely different proof of Razborov's result, using the original, one-dimensional discrepancy method. This refutes the commonly held intuition (Razborov 2003) that the original discrepancy method fails for functions such as DISJOINTNESS. More importantly, our communication lower bounds hold for a much broader class of functions for which no methods were available. Namely, fix an arbitrary function f:{0,1}n/4->{0,1} and let A be the Boolean matrix whose columns are each an application of f to some subset of the variables x1,x2,...,xn. We prove that the communication complexity of A in the bounded-error quantum model with and without prior entanglement is Omega(d), where d is the approximate degree of f. From this result, Razborov's lower bounds follow easily. Our result also establishes a large new class of total Boolean functions whose quantum communication complexity (regardless of prior entanglement) is at best polynomially smaller than their classical complexity. Our proof method is a novel combination of two ingredients. The first is a certain equivalence of approximation and orthogonality in Euclidean n-space, which follows by linear-programming duality. The second is a new construction of suitably structured matrices with low spectral norm, the pattern matrices, which we realize using matrix analysis and the Fourier transform over (Z2)n. The method of this paper has recently inspired important progress in multiparty communication complexity.
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].