期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2021
卷号：21
语种：English
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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 d2O(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 n1−1k , while having quantum query complexity k2 . 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).
关键词：Fourier analysis of Boolean functions;noisy decision tree;parity decision tree;query complexity
