Fourier growth of parity decision trees

DOI10.4230/LIPICS.CCC.2021.39MaRDI QIDQ6115402zbMATH OpenOpenAlexFDO

Authors Uma Girish, Avishay Tal, Kewen Wu

Publication date 12 July 2023

Full work available at URL https://arxiv.org/abs/2103.11604

zbMATH Keywords

Fourier analysis of Boolean functionsnoisy decision treeparity decision treequery complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

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 $ell$ is at most $d^{ell/2}cdotO(ellcdotlog(n){)}^{e}ll$. 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 $ildeOmegaleft(n^{1-1/k}ight)$, while having quantum query complexity $lceilk/2ceil$. 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 $leell-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).

Cited in

(4)

• An Optimal Separation of Randomized and Quantum Query Complexity
• Randomized versus deterministic decision tree size
• A lower bound on the trace norm of Boolean matrices and its applications
• Testing isomorphism of Boolean functions over finite abelian groups

This page was built for publication: Fourier growth of parity decision trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6115402)