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

Leibniz international proceedings in informatics

Fourier Growth of Parity Decision Trees

Uma Girish, Avishay Tal, Kewen Wu

Published Jan 1, 2021β€’ 5 citations
Publisher

Abstract

We prove that for every parity decision tree of depth d on n variables, the sum of absolute values of Fourier coefficients at level 𝓁 is at most d^{𝓁/2} β‹… O(𝓁 β‹… log(n))^𝓁. Our result is nearly tight for small values of 𝓁 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 Ξ©Μƒ(n^{1-1/k}), while having quantum query complexity ⌈ k/2βŒ‰. Our proof follows a random-walk approach, analyzing the contribution of a random path in the decision tree to the level-𝓁 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-𝓁 walks can be computed by the intermediate values of level ≀ 𝓁-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).

DOI
10.4230/lipics.ccc.2021.39

Related papers

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

An optimal separation of randomized and Quantum query complexity

Alexander A. Sherstov, Andrey A. Storozhenko, Pei Wu

We prove that for every decision tree, the absolute values of the Fourier coefficients of given order tβ‰₯1 sum to at most (cd/t)t/2(1+logn)(tβˆ’1)/2, where n is the number of variables, d is the tree depth, and c>0 is an absolute constant. This bound is essentially tight and settles a conjecture due to Tal (arxiv 2019; FOCS 2020). The bounds prior to our work degraded rapidly with t, becoming trivial already at t=√d.

ACM Symposium on Theory of Computing (STOC)β€’Jun 15, 2021β€’10 citations

An Optimal Separation of Randomized and Quantum Query Complexity

Alexander A. Sherstov, Andrey A. Storozhenko, Pei Wu

We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order $\ell\geq1$ sum to at most $c^{\ell}\sqrt{\binom{d}{\ell}(1+\log n)^{\ell-1}},$ where $n$ is the number of variables, $d$ is the tree depth, and $c>0$ is an absolute constant. This bound is essentially tight and settles a conjecture due to Tal (arxiv 2019; FOCS 2020). The bounds prior to our work degraded rapidly with $\ell,$ becoming trivial already at $\ell=\sqrt{d}.$ As an application, we obtain, for every integer $k\geq1,$ a partial Boolean function on $n$ bits that has bounded-error quantum query complexity at most $k$ and randomized query complexity $\tildeΞ©(n^{1-\frac{1}{2k}}).$ This separation of bounded-error quantum versus randomized query complexity is best possible, by the results of Aaronson and Ambainis (STOC 2015) and Bravyi, Gosset, Grier, and Schaeffer (2021). Prior to our work, the best known separation was polynomially weaker: $O(1)$ versus $Ξ©(n^{2/3-Ξ΅})$ for any $Ξ΅>0$ (Tal, FOCS 2020). As another application, we obtain an essentially optimal separation of $O(\log n)$ versus $Ξ©(n^{1-Ξ΅})$ for bounded-error quantum versus randomized communication complexity, for any $Ξ΅>0.$ The best previous separation was polynomially weaker: $O(\log n)$ versus $Ξ©(n^{2/3-Ξ΅})$ (implicit in Tal, FOCS 2020).

arXiv:2008.10223β€’Aug 24, 2020β€’5 citations

An Optimal Separation of Randomized and Quantum Query Complexity

Alexander A. Sherstov, Andrey A. Storozhenko, Pei Wu

Abstract. We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order [Formula: see text] sum to at most [Formula: see text], where [Formula: see text] is the number of variables, [Formula: see text] is the tree depth, and [Formula: see text] is an absolute constant. This bound is essentially tight and settles a conjecture due to Tal [ Towards optimal separations between quantum and randomized query complexities, in Proceedings of the Sixty-First Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2020, pp. 228–239]. The bounds prior to our work degraded rapidly with [Formula: see text], becoming trivial already at [Formula: see text]. As an application, we obtain, for every integer [Formula: see text], a partial Boolean function on [Formula: see text] bits that has bounded-error quantum query complexity at most [Formula: see text] and randomized query complexity [Formula: see text]. This separation of bounded-error quantum versus randomized query complexity is best possible, by the results of Aaronson and Ambainis [ SIAM J. Comput., 47 (2018), pp. 982–1038] and Bravyi et al. [ Classical Algorithms for Forrelation, arXiv preprint, 2021]. Prior to our work, the best known separation was polynomially weaker: [Formula: see text] versus [Formula: see text] for any [Formula: see text] [A. Tal, Towards optimal separations between quantum and randomized query complexities, in Proceedings of the Sixty-First Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2020, pp. 228–239]. As another application, we obtain an essentially optimal separation of [Formula: see text] versus [Formula: see text] for bounded-error quantum versus randomized communication complexity for any [Formula: see text]. The best previous separation was polynomially weaker: [Formula: see text] versus [Formula: see text] (this is implicit in [A. Tal, Towards optimal separations between quantum and randomized query complexities, in Proceedings of the Sixty-First Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2020, pp. 228–239]).

SIAM Journal on Computingβ€’Apr 26, 2023β€’4 citations

Fourier Growth of Communication Protocols for XOR Functions

Uma Girish, Makrand Sinha, Avishay Tal +1 more

The level-k $\ell_{1}$-Fourier weight of a Boolean function refers to the sum of absolute values of its level-k Fourier coefficients. Fourier growth refers to the growth of these weights as k grows. It has been extensively studied for various computational models, and bounds on the Fourier growth, even for the first few levels, have proven useful in learning theory, circuit lower bounds, pseudorandomness, and quantum-classical separations.In this work, we investigate the Fourier growth of certain functions that naturally arise from communication protocols for XOR functions (partial functions evaluated on the bitwise XOR of the inputs x and y to Alice and Bob). If a protocol $\mathcal C$ computes an XOR function, then $\mathcal{C}(x, y)$ is a function of the parity $x \oplus y$. This motivates us to analyze the XOR-fiber of the communication protocol $\mathcal{C}$, defined as $h(z):=\mathbb{E}_{\boldsymbol{x}, \boldsymbol{y}}[\mathcal{C}(\boldsymbol{x}, \boldsymbol{y}) \mid \boldsymbol{x} \oplus \boldsymbol{y}=z]$.We present improved Fourier growth bounds for the XOR-fibers of randomized protocols that communicate d bits. For the first level, we show a tight $O(\sqrt{d})$ bound and obtain a new coin theorem, as well as an alternative proof for the tight randomized communication lower bound for the Gap-Hamming problem. For the second level, we show an $d^{3 / 2} \cdot \operatorname{polylog}(n)$ bound, which improves the previous $O\left(d^{2}\right)$ bound by Girish, Raz, and Tal (ITCS 2021) and implies a polynomial improvement on the randomized communication lower bound for the XOR-lift of the Forrelation problem, which extends the quantum-classical gap for this problem.Our analysis is based on a new way of adaptively partitioning a relatively large set in Gaussian space to control its moments in all directions. We achieve this via martingale arguments and allowing protocols to transmit real values. We also show a connection between Fourier growth and lifting theorems with constant-sized gadgets as a potential approach to prove optimal bounds for the second level and beyond.

arXiv:2307.13926β€’Annual Symposium on Foundations of Computer Scienceβ€’Nov 6, 2023β€’1 citation

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β€’17 citations
We prove that for every parity decision tree of depth d on n variables, the sum of absolute values of Fourier coefficients at level 𝓁 is at most d^{𝓁/2} β‹… O(𝓁 β‹… log(n))^𝓁. Our result is nearly tight for small values of 𝓁 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 Ξ©Μƒ(n^{1-1/k}), while having quantum query complexity ⌈ k/2βŒ‰. Our proof follows a random-walk approach, analyzing the contribution of a random path in the decision tree to the level-𝓁 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-𝓁 walks can be computed by the intermediate values of level ≀ 𝓁-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).
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).
We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order β„“β‰₯1\ell\geq1β„“β‰₯1 sum to at most cβ„“(dβ„“)(1+log⁑n)β„“βˆ’1,c^{\ell}\sqrt{\binom{d}{\ell}(1+\log n)^{\ell-1}},cβ„“(β„“d​)(1+logn)β„“βˆ’1​, where nnn is the number of variables, ddd is the tree depth, and c>0c>0c>0 is an absolute constant. This bound is essentially tight and settles a conjecture due to Tal (arxiv 2019; FOCS 2020). The bounds prior to our work degraded rapidly with β„“,\ell,β„“, becoming trivial already at β„“=d.\ell=\sqrt{d}.β„“=d​. As an application, we obtain, for every integer kβ‰₯1,k\geq1,kβ‰₯1, a partial Boolean function on nnn bits that has bounded-error quantum query complexity at most kkk and randomized query complexity Ξ©~(n1βˆ’12k).\tildeΞ©(n^{1-\frac{1}{2k}}).Ξ©~(n1βˆ’2k1​). This separation of bounded-error quantum versus randomized query complexity is best possible, by the results of Aaronson and Ambainis (STOC 2015) and Bravyi, Gosset, Grier, and Schaeffer (2021). Prior to our work, the best known separation was polynomially weaker: O(1)O(1)O(1) versus Ξ©(n2/3βˆ’Ξ΅)Ξ©(n^{2/3-Ξ΅})Ξ©(n2/3βˆ’Ξ΅) for any Ξ΅>0Ξ΅>0Ξ΅>0 (Tal, FOCS 2020). As another application, we obtain an essentially optimal separation of O(log⁑n)O(\log n)O(logn) versus Ξ©(n1βˆ’Ξ΅)Ξ©(n^{1-Ξ΅})Ξ©(n1βˆ’Ξ΅) for bounded-error quantum versus randomized communication complexity, for any Ξ΅>0.Ξ΅>0.Ξ΅>0. The best previous separation was polynomially weaker: O(log⁑n)O(\log n)O(logn) versus Ξ©(n2/3βˆ’Ξ΅)Ξ©(n^{2/3-Ξ΅})Ξ©(n2/3βˆ’Ξ΅) (implicit in Tal, FOCS 2020).
Abstract. We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order [Formula: see text] sum to at most [Formula: see text], where [Formula: see text] is the number of variables, [Formula: see text] is the tree depth, and [Formula: see text] is an absolute constant. This bound is essentially tight and settles a conjecture due to Tal [ Towards optimal separations between quantum and randomized query complexities, in Proceedings of the Sixty-First Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2020, pp. 228–239]. The bounds prior to our work degraded rapidly with [Formula: see text], becoming trivial already at [Formula: see text]. As an application, we obtain, for every integer [Formula: see text], a partial Boolean function on [Formula: see text] bits that has bounded-error quantum query complexity at most [Formula: see text] and randomized query complexity [Formula: see text]. This separation of bounded-error quantum versus randomized query complexity is best possible, by the results of Aaronson and Ambainis [ SIAM J. Comput., 47 (2018), pp. 982–1038] and Bravyi et al. [ Classical Algorithms for Forrelation, arXiv preprint, 2021]. Prior to our work, the best known separation was polynomially weaker: [Formula: see text] versus [Formula: see text] for any [Formula: see text] [A. Tal, Towards optimal separations between quantum and randomized query complexities, in Proceedings of the Sixty-First Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2020, pp. 228–239]. As another application, we obtain an essentially optimal separation of [Formula: see text] versus [Formula: see text] for bounded-error quantum versus randomized communication complexity for any [Formula: see text]. The best previous separation was polynomially weaker: [Formula: see text] versus [Formula: see text] (this is implicit in [A. Tal, Towards optimal separations between quantum and randomized query complexities, in Proceedings of the Sixty-First Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2020, pp. 228–239]).
The level-k β„“1\ell_{1}β„“1​-Fourier weight of a Boolean function refers to the sum of absolute values of its level-k Fourier coefficients. Fourier growth refers to the growth of these weights as k grows. It has been extensively studied for various computational models, and bounds on the Fourier growth, even for the first few levels, have proven useful in learning theory, circuit lower bounds, pseudorandomness, and quantum-classical separations.In this work, we investigate the Fourier growth of certain functions that naturally arise from communication protocols for XOR functions (partial functions evaluated on the bitwise XOR of the inputs x and y to Alice and Bob). If a protocol C\mathcal CC computes an XOR function, then C(x,y)\mathcal{C}(x, y)C(x,y) is a function of the parity xβŠ•yx \oplus yxβŠ•y. This motivates us to analyze the XOR-fiber of the communication protocol C\mathcal{C}C, defined as h(z):=Ex,y[C(x,y)∣xβŠ•y=z]h(z):=\mathbb{E}_{\boldsymbol{x}, \boldsymbol{y}}[\mathcal{C}(\boldsymbol{x}, \boldsymbol{y}) \mid \boldsymbol{x} \oplus \boldsymbol{y}=z]h(z):=Ex,y​[C(x,y)∣xβŠ•y=z].We present improved Fourier growth bounds for the XOR-fibers of randomized protocols that communicate d bits. For the first level, we show a tight O(d)O(\sqrt{d})O(d​) bound and obtain a new coin theorem, as well as an alternative proof for the tight randomized communication lower bound for the Gap-Hamming problem. For the second level, we show an d3/2β‹…polylog⁑(n)d^{3 / 2} \cdot \operatorname{polylog}(n)d3/2β‹…polylog(n) bound, which improves the previous O(d2)O\left(d^{2}\right)O(d2) bound by Girish, Raz, and Tal (ITCS 2021) and implies a polynomial improvement on the randomized communication lower bound for the XOR-lift of the Forrelation problem, which extends the quantum-classical gap for this problem.Our analysis is based on a new way of adaptively partitioning a relatively large set in Gaussian space to control its moments in all directions. We achieve this via martingale arguments and allowing protocols to transmit real values. We also show a connection between Fourier growth and lifting theorems with constant-sized gadgets as a potential approach to prove optimal bounds for the second level and beyond.
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.