Document Open Access Logo

Fourier Growth of Parity Decision Trees

Authors Uma Girish , Avishay Tal , Kewen Wu

PDF
Thumbnail PDF

File

LIPIcs.CCC.2021.39.pdf
  • Filesize: 1.08 MB
  • 36 pages

Document Identifiers

Author Details

Uma Girish
  • Princeton University, NJ, USA
Avishay Tal
  • University of California at Berkeley, CA, USA
Kewen Wu
  • University of California at Berkeley, CA, USA

Funding

  • Girish, Uma: Research supported by the Simons Collaboration on Algorithms and Geometry, by a Simons Investigator Award and by the National Science Foundation grant No. CCF-1714779.

Acknowledgements

We thank anonymous reviewers for helpful comments.

Cite AsGet BibTex

Uma Girish, Avishay Tal, and Kewen Wu. Fourier Growth of Parity Decision Trees. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 39:1-39:36, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.CCC.2021.39

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

Subject Classification

ACM Subject Classification
  • Theory of computation → Oracles and decision trees
  • Theory of computation → Communication complexity
  • Theory of computation → Quantum complexity theory
Keywords
  • Fourier analysis of Boolean functions
  • noisy decision tree
  • parity decision tree
  • query complexity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Scott Aaronson and Andris Ambainis. Forrelation: A problem that optimally separates quantum from classical computing. SIAM J. Comput., 47(3):982-1038, 2018. Google Scholar
  2. Nikhil Bansal and Makrand Sinha. dollarkdollar-forrelation optimally separates quantum and classical query complexity. Electron. Colloquium Comput. Complex., 27:127, 2020. Google Scholar
  3. Shalev Ben-David and Eric Blais. A tight composition theorem for the randomized query complexity of partial functions: Extended abstract. In FOCS, pages 240-246. IEEE, 2020. Google Scholar
  4. Eric Blais, Li-Yang Tan, and Andrew Wan. An inequality for the fourier spectrum of parity decision trees. CoRR, abs/1506.01055, 2015. Google Scholar
  5. Aline Bonami. Étude des coefficients de fourier des fonctions de l^p(g). Annales de l'institut Fourier, 20(2):335-402, 1970. URL: http://eudml.org/doc/74019.
  6. Joseph Briggs and Wesley Pegden. Extremal collections of k-uniform vectors. arXiv preprint, 2018. URL: http://arxiv.org/abs/1801.09609.
  7. Arkadev Chattopadhyay, Yuval Filmus, Sajin Koroth, Or Meir, and Toniann Pitassi. Query-to-communication lifting for BPP using inner product. In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, volume 132 of LIPIcs, pages 35:1-35:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.ICALP.2019.35.
  8. Eshan Chattopadhyay, Jason Gaitonde, Chin Ho Lee, Shachar Lovett, and Abhishek Shetty. Fractional pseudorandom generators from any fourier level. CoRR, abs/2008.01316, 2020. URL: http://arxiv.org/abs/2008.01316.
  9. Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, and Shachar Lovett. Pseudorandom generators from polarizing random walks. Theory Comput., 15:1-26, 2019. Google Scholar
  10. Eshan Chattopadhyay, Pooya Hatami, Shachar Lovett, and Avishay Tal. Pseudorandom generators from the second fourier level and applications to AC0 with parity gates. In ITCS, volume 124 of LIPIcs, pages 22:1-22:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. Google Scholar
  11. Eshan Chattopadhyay, Pooya Hatami, Omer Reingold, and Avishay Tal. Improved pseudorandomness for unordered branching programs through local monotonicity. In STOC, pages 363-375. ACM, 2018. Google Scholar
  12. Gil Cohen, Noam Peri, and Amnon Ta-Shma. Expander random walks: A fourier-analytic approach. Electron. Colloquium Comput. Complex., 27:163, 2020. Google Scholar
  13. Gil Cohen and Igor Shinkar. The complexity of DNF of parities. In ITCS, pages 47-58. ACM, 2016. Google Scholar
  14. Dmitry Gavinsky. Entangled simultaneity versus classical interactivity in communication complexity. In Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, STOC '16, page 877–884, New York, NY, USA, 2016. Association for Computing Machinery. URL: https://doi.org/10.1145/2897518.2897545.
  15. Uma Girish, Ran Raz, and Avishay Tal. Quantum versus randomized communication complexity, with efficient players. In ITCS, volume 185 of LIPIcs, pages 54:1-54:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. Google Scholar
  16. Uma Girish, Ran Raz, and Wei Zhan. Lower bounds for XOR of forrelations. Electron. Colloquium Comput. Complex., 27:101, 2020. Google Scholar
  17. Parikshit Gopalan, Rocco A. Servedio, Avishay Tal, and Avi Wigderson. Degree and sensitivity: tails of two distributions. Electron. Colloquium Comput. Complex., 23:69, 2016. Google Scholar
  18. Hamed Hatami, Kaave Hosseini, and Shachar Lovett. Structure of protocols for XOR functions. SIAM J. Comput., 47(1):208-217, 2018. Google Scholar
  19. Joshua Brown Kramer. On the most weight w vectors in a dimension k binary code. Electron. J. Comb., 17(1), 2010. Google Scholar
  20. Raghav Kulkarni, Youming Qiao, and Xiaoming Sun. On the power of parity queries in boolean decision trees. In TAMC, volume 9076 of Lecture Notes in Computer Science, pages 99-109. Springer, 2015. Google Scholar
  21. Eyal Kushilevitz and Yishay Mansour. Learning decision trees using the fourier spectrum. SIAM J. Comput., 22(6):1331-1348, 1993. Google Scholar
  22. Chin Ho Lee. Fourier bounds and pseudorandom generators for product tests. In Computational Complexity Conference, volume 137 of LIPIcs, pages 7:1-7:25. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. Google Scholar
  23. Nikhil S. Mande and Swagato Sanyal. On parity decision trees for fourier-sparse boolean functions. In FSTTCS, volume 182 of LIPIcs, pages 29:1-29:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. Google Scholar
  24. Yishay Mansour. An o(n^(log log n)) learning algorithm for DNF under the uniform distribution. J. Comput. Syst. Sci., 50(3):543-550, 1995. Google Scholar
  25. Ashley Montanaro, Harumichi Nishimura, and Rudy Raymond. Unbounded-error quantum query complexity. Theor. Comput. Sci., 412(35):4619-4628, 2011. URL: https://doi.org/10.1016/j.tcs.2011.04.043.
  26. Ashley Montanaro and Tobias Osborne. On the communication complexity of XOR functions. CoRR, abs/0909.3392, 2009. URL: http://arxiv.org/abs/0909.3392.
  27. Joseph Naor and Moni Naor. Small-bias probability spaces: Efficient constructions and applications. SIAM J. Comput., 22(4):838-856, 1993. Google Scholar
  28. Ryan O'Donnell. Open problems in analysis of boolean functions. CoRR, abs/1204.6447, 2012. URL: http://arxiv.org/abs/1204.6447.
  29. Ryan O'Donnell. Analysis of Boolean Functions. Cambridge University Press, 2014. Google Scholar
  30. Ryan O'Donnell and Rocco A. Servedio. Learning monotone decision trees in polynomial time. SIAM J. Comput., 37(3):827-844, 2007. Google Scholar
  31. Ryan O'Donnell, John Wright, Yu Zhao, Xiaorui Sun, and Li-Yang Tan. A composition theorem for parity kill number. In Computational Complexity Conference, pages 144-154. IEEE Computer Society, 2014. Google Scholar
  32. Omer Reingold, Thomas Steinke, and Salil P. Vadhan. Pseudorandomness for regular branching programs via fourier analysis. In APPROX-RANDOM, volume 8096 of Lecture Notes in Computer Science, pages 655-670. Springer, 2013. Google Scholar
  33. Swagato Sanyal. Fourier sparsity and dimension. Theory Comput., 15:1-13, 2019. Google Scholar
  34. Alexander A. Sherstov, Andrey A. Storozhenko, and Pei Wu. An optimal separation of randomized and quantum query complexity. Electron. Colloquium Comput. Complex., 27:128, 2020. Google Scholar
  35. Amir Shpilka, Avishay Tal, and Ben lee Volk. On the structure of boolean functions with small spectral norm. Comput. Complex., 26(1):229-273, 2017. Google Scholar
  36. Avishay Tal. Tight bounds on the fourier spectrum of AC0. In Computational Complexity Conference, volume 79 of LIPIcs, pages 15:1-15:31. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. Google Scholar
  37. Avishay Tal. Towards optimal separations between quantum and randomized query complexities. In FOCS, pages 228-239. IEEE, 2020. Google Scholar
  38. Hing Yin Tsang, Chung Hoi Wong, Ning Xie, and Shengyu Zhang. Fourier sparsity, spectral norm, and the log-rank conjecture. In FOCS, pages 658-667. IEEE Computer Society, 2013. Google Scholar
  39. Zhiqiang Zhang and Yaoyun Shi. Communication complexities of symmetric XOR functions. Quantum Inf. Comput., 9(3&4):255-263, 2009. Google Scholar
  40. Zhiqiang Zhang and Yaoyun Shi. On the parity complexity measures of boolean functions. Theor. Comput. Sci., 411(26-28):2612-2618, 2010. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact