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

Parity Decision Trees of Depth $O(4^d \log\|\widehat f\|_1)$ for Boolean Functions $f$ of $F_2$-Degree $d$

Shengyu Zhang

Published Nov 2, 2026• 0 citations
arXivHTMLPDF

Abstract

Let $f\colon F_2^n\to\{-1,+1\}$ have $F_2$-degree $d\ge2$. We prove that its deterministic parity decision tree depth satisfies \[ D_{\oplus} (f)= O(4^d \log_2\|\widehat f\|_1) = O(4^d \log_2 s(f)), \] where $\|\widehat f\|_1=\sum_ξ|\widehat f(ξ)|$ is the Fourier spectral norm and $s(f)$ is the Fourier sparsity. The bound is linear in the logarithm of the spectral norm for every fixed degree, with singly exponential dependence on $d$. This improves the previously best known bound of $O(2^{d^2/2} \log^{d-2} \|\widehat f\|_1)$ due to Tsang, Wong, Xie and Zhang (FOCS 2013). Our result establishes the log-rank conjecture for $\mathrm{XOR}$ functions of $F_2$-degree $O(\log\log s(f))$, extending the previously accessible range $d=O(1)$. The proof combines field lifting, multiplicative derivatives, a multiplicity-based generic-rank comparison, a Schur-complement vanishing argument, and dimension-preserving descent to $F_2$ to lower the degree on every coset of a common subspace.

DOI
10.48550/arxiv.2611.03452

Related papers

Parity Decision Tree Complexity is Greater Than Granularity

Anastasiya Chistopolskaya, Vladimir V. Podolskii

We prove a new lower bound on the parity decision tree complexity $\mathsf{D}_{\oplus}(f)$ of a Boolean function $f$. Namely, granularity of the Boolean function $f$ is the smallest $k$ such that all Fourier coefficients of $f$ are integer multiples of $1/2^k$. We show that $\mathsf{D}_{\oplus}(f)\geq k+1$. This lower bound is an improvement of lower bounds through the sparsity of $f$ and through the degree of $f$ over $\mathbb{F}_2$. Using our lower bound we determine the exact parity decision tree complexity of several important Boolean functions including majority and recursive majority. For majority the complexity is $n - \mathsf{B}(n)+1$, where $\mathsf{B}(n)$ is the number of ones in the binary representation of $n$. For recursive majority the complexity is $\frac{n+1}{2}$. Finally, we provide an example of a function for which our lower bound is not tight. Our results imply new lower bound of $n - \mathsf{B}(n)$ on the multiplicative complexity of majority.

arXiv:1810.08668•Oct 19, 2018•8 citations

Towards Stronger Counterexamples to the Log-Approximate-Rank Conjecture

Arkadev Chattopadhyay, Ankit Garg, Suhail Sherif

We give improved separations for the query complexity analogue of the log-approximate-rank conjecture i.e. we show that there are a plethora of total Boolean functions on n input bits, each of which has approximate Fourier sparsity at most O(n³) and randomized parity decision tree complexity Θ(n). This improves upon the recent work of Chattopadhyay, Mande and Sherif [Chattopadhyay et al., 2020] both qualitatively (in terms of designing a large number of examples) and quantitatively (shrinking the gap from quartic to cubic). We leave open the problem of proving a randomized communication complexity lower bound for XOR compositions of our examples. A linear lower bound would lead to new and improved refutations of the log-approximate-rank conjecture. Moreover, if any of these compositions had even a sub-linear cost randomized communication protocol, it would demonstrate that randomized parity decision tree complexity does not lift to randomized communication complexity in general (with the XOR gadget).

Leibniz international proceedings in informatics•Jan 1, 2021•5 citations

Towards Stronger Counterexamples to the Log-Approximate-Rank Conjecture.

Arkadev Chattopadhyay, Ankit Garg, Suhail Sherif

We give improved separations for the query complexity analogue of the log-approximate-rank conjecture i.e. we show that there are a plethora of total Boolean functions on $n$ input bits, each of which has approximate Fourier sparsity at most $O(n^3)$ and randomized parity decision tree complexity $\Theta(n)$. This improves upon the recent work of Chattopadhyay, Mande and Sherif (JACM '20) both qualitatively (in terms of designing a large number of examples) and quantitatively (improving the gap from quartic to cubic). We leave open the problem of proving a randomized communication complexity lower bound for XOR compositions of our examples. A linear lower bound would lead to new and improved refutations of the log-approximate-rank conjecture. Moreover, if any of these compositions had even a sub-linear cost randomized communication protocol, it would demonstrate that randomized parity decision tree complexity does not lift to randomized communication complexity in general (with the XOR gadget).

Electronic colloquium on computational complexity•Jan 1, 2020•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

Towards Stronger Counterexamples to the Log-Approximate-Rank Conjecture

Arkadev Chattopadhyay, Ankit Garg, Suhail Sherif

We give improved separations for the query complexity analogue of the log-approximate-rank conjecture i.e. we show that there are a plethora of total Boolean functions on $n$ input bits, each of which has approximate Fourier sparsity at most $O(n^3)$ and randomized parity decision tree complexity $Θ(n)$. This improves upon the recent work of Chattopadhyay, Mande and Sherif (JACM '20) both qualitatively (in terms of designing a large number of examples) and quantitatively (improving the gap from quartic to cubic). We leave open the problem of proving a randomized communication complexity lower bound for XOR compositions of our examples. A linear lower bound would lead to new and improved refutations of the log-approximate-rank conjecture. Moreover, if any of these compositions had even a sub-linear cost randomized communication protocol, it would demonstrate that randomized parity decision tree complexity does not lift to randomized communication complexity in general (with the XOR gadget).

arXiv:2009.02717•Sep 6, 2020•1 citation

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Ω\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).

arXiv:2103.11604•Leibniz international proceedings in informatics•Jan 1, 2021•16 citations
Parity Decision Trees of Depth O(4dlog⁡∥f^∥1)O(4^d \log\|\widehat f\|_1)O(4dlog∥f​∥1​) for Boolean Functions fff of F2F_2F2​-Degree ddd
Let f ⁣:F2n→{−1,+1}f\colon F_2^n\to\{-1,+1\}f:F2n​→{−1,+1} have F2F_2F2​-degree d≥2d\ge2d≥2. We prove that its deterministic parity decision tree depth satisfies [ D_{\oplus} (f)= O(4^d \log_2|\widehat f|_1) = O(4^d \log_2 s(f)), ] where ∥f^∥1=∑ξ∣f^(ξ)∣\|\widehat f\|_1=\sum_ξ|\widehat f(ξ)|∥f​∥1​=∑ξ​∣f​(ξ)∣ is the Fourier spectral norm and s(f)s(f)s(f) is the Fourier sparsity. The bound is linear in the logarithm of the spectral norm for every fixed degree, with singly exponential dependence on ddd. This improves the previously best known bound of O(2d2/2log⁡d−2∥f^∥1)O(2^{d^2/2} \log^{d-2} \|\widehat f\|_1)O(2d2/2logd−2∥f​∥1​) due to Tsang, Wong, Xie and Zhang (FOCS 2013). Our result establishes the log-rank conjecture for XOR\mathrm{XOR}XOR functions of F2F_2F2​-degree O(log⁡log⁡s(f))O(\log\log s(f))O(loglogs(f)), extending the previously accessible range d=O(1)d=O(1)d=O(1). The proof combines field lifting, multiplicative derivatives, a multiplicity-based generic-rank comparison, a Schur-complement vanishing argument, and dimension-preserving descent to F2F_2F2​ to lower the degree on every coset of a common subspace.
We prove a new lower bound on the parity decision tree complexity D⊕(f)\mathsf{D}_{\oplus}(f)D⊕​(f) of a Boolean function fff. Namely, granularity of the Boolean function fff is the smallest kkk such that all Fourier coefficients of fff are integer multiples of 1/2k1/2^k1/2k. We show that D⊕(f)≥k+1\mathsf{D}_{\oplus}(f)\geq k+1D⊕​(f)≥k+1. This lower bound is an improvement of lower bounds through the sparsity of fff and through the degree of fff over F2\mathbb{F}_2F2​. Using our lower bound we determine the exact parity decision tree complexity of several important Boolean functions including majority and recursive majority. For majority the complexity is n−B(n)+1n - \mathsf{B}(n)+1n−B(n)+1, where B(n)\mathsf{B}(n)B(n) is the number of ones in the binary representation of nnn. For recursive majority the complexity is n+12\frac{n+1}{2}2n+1​. Finally, we provide an example of a function for which our lower bound is not tight. Our results imply new lower bound of n−B(n)n - \mathsf{B}(n)n−B(n) on the multiplicative complexity of majority.
We give improved separations for the query complexity analogue of the log-approximate-rank conjecture i.e. we show that there are a plethora of total Boolean functions on n input bits, each of which has approximate Fourier sparsity at most O(n³) and randomized parity decision tree complexity Θ(n). This improves upon the recent work of Chattopadhyay, Mande and Sherif [Chattopadhyay et al., 2020] both qualitatively (in terms of designing a large number of examples) and quantitatively (shrinking the gap from quartic to cubic). We leave open the problem of proving a randomized communication complexity lower bound for XOR compositions of our examples. A linear lower bound would lead to new and improved refutations of the log-approximate-rank conjecture. Moreover, if any of these compositions had even a sub-linear cost randomized communication protocol, it would demonstrate that randomized parity decision tree complexity does not lift to randomized communication complexity in general (with the XOR gadget).
We give improved separations for the query complexity analogue of the log-approximate-rank conjecture i.e. we show that there are a plethora of total Boolean functions on nnn input bits, each of which has approximate Fourier sparsity at most O(n3)O(n^3)O(n3) and randomized parity decision tree complexity Θ(n)\Theta(n)Θ(n). This improves upon the recent work of Chattopadhyay, Mande and Sherif (JACM '20) both qualitatively (in terms of designing a large number of examples) and quantitatively (improving the gap from quartic to cubic). We leave open the problem of proving a randomized communication complexity lower bound for XOR compositions of our examples. A linear lower bound would lead to new and improved refutations of the log-approximate-rank conjecture. Moreover, if any of these compositions had even a sub-linear cost randomized communication protocol, it would demonstrate that randomized parity decision tree complexity does not lift to randomized communication complexity in general (with the XOR gadget).
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 give improved separations for the query complexity analogue of the log-approximate-rank conjecture i.e. we show that there are a plethora of total Boolean functions on nnn input bits, each of which has approximate Fourier sparsity at most O(n3)O(n^3)O(n3) and randomized parity decision tree complexity Θ(n)Θ(n)Θ(n). This improves upon the recent work of Chattopadhyay, Mande and Sherif (JACM '20) both qualitatively (in terms of designing a large number of examples) and quantitatively (improving the gap from quartic to cubic). We leave open the problem of proving a randomized communication complexity lower bound for XOR compositions of our examples. A linear lower bound would lead to new and improved refutations of the log-approximate-rank conjecture. Moreover, if any of these compositions had even a sub-linear cost randomized communication protocol, it would demonstrate that randomized parity decision tree complexity does not lift to randomized communication complexity in general (with the XOR gadget).
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Ω\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).