Document Open Access Logo

Fourier Growth of Structured 𝔽₂-Polynomials and Applications

Authors Jarosław Błasiok, Peter Ivanov, Yaonan Jin, Chin Ho Lee, Rocco A. Servedio, Emanuele Viola

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2021.53.pdf
  • Filesize: 0.82 MB
  • 20 pages

Document Identifiers

Author Details

Jarosław Błasiok
  • Columbia University, New York, NY, USA
Peter Ivanov
  • Northeastern University, Boston, MA, USA
Yaonan Jin
  • Columbia University, New York, NY, USA
Chin Ho Lee
  • Columbia University, New York, NY, USA
Rocco A. Servedio
  • Columbia University, New York, NY, USA
Emanuele Viola
  • Northeastern University, Boston, MA, USA

Funding

  • Błasiok, Jarosław: Junior Fellowship from the Simons Society of Fellows.
  • Ivanov, Peter: NSF awards CCF-1813930 and CCF-2114116.
  • Jin, Yaonan: NSF IIS-1838154, NSF CCF-1703925, NSF CCF-1814873 and NSF CCF-1563155.
  • Lee, Chin Ho: Croucher Foundation and Simons Collaboration on Algorithms and Geometry.
  • Servedio, Rocco A.: NSF grants CCF-1814873, IIS-1838154, CCF-1563155, and Simons Collaboration on Algorithms and Geometry.
  • Viola, Emanuele: NSF awards CCF-1813930 and CCF-2114116.

Acknowledgements

We thank Shivam Nadimpalli for stimulating discussions at the early stage of the project.

Cite AsGet BibTex

Jarosław Błasiok, Peter Ivanov, Yaonan Jin, Chin Ho Lee, Rocco A. Servedio, and Emanuele Viola. Fourier Growth of Structured 𝔽₂-Polynomials and Applications. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 53:1-53:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2021.53

Abstract

We analyze the Fourier growth, i.e. the L₁ Fourier weight at level k (denoted L_{1,k}), of various well-studied classes of "structured" m F₂-polynomials. This study is motivated by applications in pseudorandomness, in particular recent results and conjectures due to [Chattopadhyay et al., 2019; Chattopadhyay et al., 2019; Eshan Chattopadhyay et al., 2020] which show that upper bounds on Fourier growth (even at level k = 2) give unconditional pseudorandom generators. Our main structural results on Fourier growth are as follows: - We show that any symmetric degree-d m F₂-polynomial p has L_{1,k}(p) ≤ Pr [p = 1] ⋅ O(d)^k. This quadratically strengthens an earlier bound that was implicit in [Omer Reingold et al., 2013]. - We show that any read-Δ degree-d m F₂-polynomial p has L_{1,k}(p) ≤ Pr [p = 1] ⋅ (k Δ d)^{O(k)}. - We establish a composition theorem which gives L_{1,k} bounds on disjoint compositions of functions that are closed under restrictions and admit L_{1,k} bounds. Finally, we apply the above structural results to obtain new unconditional pseudorandom generators and new correlation bounds for various classes of m F₂-polynomials.

Subject Classification

ACM Subject Classification
  • Theory of computation → Pseudorandomness and derandomization
  • Theory of computation → Circuit complexity
Keywords
  • Fourier analysis
  • Pseudorandomness
  • Fourier growth

Metrics

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

Related Versions

References

  1. Nikhil Bansal and Makrand Sinha. K-forrelation optimally separates quantum and classical query complexity. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021, New York, NY, USA, 2021. URL: https://doi.org/10.1145/3406325.3451040.
  2. Ido Ben-Eliezer, Rani Hod, and Shachar Lovett. Random low-degree polynomials are hard to approximate. Comput. Complexity, 21(1):63-81, 2012. URL: https://doi.org/10.1007/s00037-011-0020-6.
  3. Nayantara Bhatnagar, Parikshit Gopalan, and Richard J. Lipton. Symmetric polynomials over ℤ_m and simultaneous communication protocols. J. Comput. System Sci., 72(2):252-285, 2006. URL: https://doi.org/10.1016/j.jcss.2005.06.007.
  4. Eric Blais, Li-Yang Tan, and Andrew Wan. An inequality for the fourier spectrum of parity decision trees, 2015. URL: http://arxiv.org/abs/1506.01055.
  5. Andrej Bogdanov and Emanuele Viola. Pseudorandom bits for polynomials. SIAM J. Comput., 39(6):2464-2486, 2010. URL: https://doi.org/10.1137/070712109.
  6. Ravi Boppana, Johan Håstad, Chin Ho Lee, and Emanuele Viola. Bounded independence versus symmetric tests. ACM Trans. Comput. Theory, 11(4):Art. 21, 27, 2019. URL: https://doi.org/10.1145/3337783.
  7. Sourav Chakraborty, Nikhil S. Mande, Rajat Mittal, Tulasimohan Molli, Manaswi Paraashar, and Swagato Sanyal. Tight chang’s-lemma-type bounds for boolean functions. CoRR, abs/2012.02335, 2020. URL: http://arxiv.org/abs/2012.02335.
  8. Eshan Chattopadhyay, Jason Gaitonde, Chin Ho Lee, Shachar Lovett, and Abhishek Shetty. Fractional Pseudorandom Generators from Any Fourier Level, 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:Paper No. 10, 26, 2019. URL: https://doi.org/10.4086/toc.2019.v015a010.
  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 10th Innovations in Theoretical Computer Science, volume 124 of LIPIcs, 2019. URL: https://doi.org/10.4230/LIPIcs.ITCS.2019.22.
  11. Eshan Chattopadhyay, Pooya Hatami, Omer Reingold, and Avishay Tal. Improved pseudorandomness for unordered branching programs through local monotonicity. In STOC'18 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 363-375. ACM, New York, 2018. URL: https://doi.org/10.1145/3188745.3188800.
  12. Lijie Chen, Xin Lyu, and R. Ryan Williams. Almost-everywhere circuit lower bounds from non-trivial derandomization. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 1-12, 2020. URL: https://doi.org/10.1109/FOCS46700.2020.00009.
  13. Gil Cohen, Noam Peri, and Amnon Ta-Shma. Expander random walks: A fourier-analytic approach. Electron. Colloquium Comput. Complex., 27:163, 2020. URL: https://eccc.weizmann.ac.il/report/2020/163.
  14. Dean Doron, Pooya Hatami, and William M. Hoza. Log-seed pseudorandom generators via iterated restrictions. In 35th Computational Complexity Conference, volume 169 of LIPIcs, 2020. URL: https://doi.org/10.4230/LIPIcs.CCC.2020.6.
  15. Bill Fefferman, Ronen Shaltiel, Christopher Umans, and Emanuele Viola. On beating the hybrid argument. Theory Comput., 9:809-843, 2013. URL: https://doi.org/10.4086/toc.2013.v009a026.
  16. Uma Girish, Ran Raz, and Avishay Tal. Quantum Versus Randomized Communication Complexity, with Efficient Players. In James R. Lee, editor, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021), volume 185 of LIPIcs, 2021. URL: https://doi.org/10.4230/LIPIcs.ITCS.2021.54.
  17. Uma Girish, Ran Raz, and Wei Zhan. Lower bounds for XOR of forrelations, 2020. URL: http://arxiv.org/abs/2007.03631.
  18. Uma Girish, Avishay Tal, and Kewen Wu. Fourier Growth of Parity Decision Trees. In Valentine Kabanets, editor, 36th Computational Complexity Conference (CCC 2021), volume 200 of LIPIcs, 2021. URL: https://doi.org/10.4230/LIPIcs.CCC.2021.39.
  19. Parikshit Gopalan, Rocco A. Servedio, Avishay Tal, and Avi Wigderson. Degree and sensitivity: tails of two distributions. Electron. Colloquium Comput. Complex., 23:69, 2016. URL: http://eccc.hpi-web.de/report/2016/069.
  20. Ben Green and Terence Tao. The distribution of polynomials over finite fields, with applications to the Gowers norms. Contrib. Discrete Math., 4(2):1-36, 2009. Google Scholar
  21. Frederic Green, Daniel Kreymer, and Emanuele Viola. Block-symmetric polynomials correlate with parity better than symmetric. Comput. Complexity, 26(2):323-364, 2017. URL: https://doi.org/10.1007/s00037-017-0153-3.
  22. Chin Ho Lee. Fourier bounds and pseudorandom generators for product tests. In 34th Computational Complexity Conference, volume 137 of LIPIcs, 2019. URL: https://doi.org/10.4230/LIPIcs.CCC.2019.7.
  23. Chin Ho Lee and Emanuele Viola. More on bounded independence plus noise: pseudorandom generators for read-once polynomials. Theory Comput., 16:Paper No. 7, 50, 2020. URL: https://doi.org/10.4086/toc.2020.v016a007.
  24. Shachar Lovett. Unconditional pseudorandom generators for low-degree polynomials. Theory Comput., 5:69-82, 2009. URL: https://doi.org/10.4086/toc.2009.v005a003.
  25. Shachar Lovett, Roy Meshulam, and Alex Samorodnitsky. Inverse conjecture for the Gowers norm is false. Theory Comput., 7:131-145, 2011. URL: https://doi.org/10.4086/toc.2011.v007a009.
  26. Yishay Mansour. An O(n^log log n) learning algorithm for DNF under the uniform distribution. J. Comput. System Sci., 50(3, part 3):543-550, 1995. Fifth Annual Workshop on Computational Learning Theory (COLT) (Pittsburgh, PA, 1992). URL: https://doi.org/10.1006/jcss.1995.1043.
  27. Raghu Meka, Omer Reingold, and Avishay Tal. Pseudorandom generators for width-3 branching programs. In STOC'19 - Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 626-637. ACM, New York, 2019. URL: https://doi.org/10.1145/3313276.3316319.
  28. Noam Nisan. Pseudorandom generators for space-bounded computation. Combinatorica, 12(4):449-461, 1992. URL: https://doi.org/10.1007/BF01305237.
  29. Ryan O'Donnell. Analysis of Boolean Functions. Cambridge University Press, 2014. URL: https://doi.org/10.1017/CBO9781139814782.
  30. Ryan O'Donnell and Rocco A. Servedio. Learning monotone decision trees in polynomial time. SIAM J. Comput., 37(3):827-844, 2007. URL: https://doi.org/10.1137/060669309.
  31. Ran Raz and Avishay Tal. Oracle separation of BQP and PH. In STOC'19 - Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 13-23. ACM, New York, 2019. URL: https://doi.org/10.1145/3313276.3316315.
  32. Alexander A. Razborov. Lower bounds on the dimension of schemes of bounded depth in a complete basis containing the logical addition function. Mat. Zametki, 41(4):598-607, 623, 1987. Google Scholar
  33. Omer Reingold, Thomas Steinke, and Salil P. Vadhan. Pseudorandomness for regular branching programs via fourier analysis. In RANDOM 2013, volume 8096 of Lecture Notes in Computer Science, pages 655-670, 2013. Google Scholar
  34. Rocco A. Servedio and Li-Yang Tan. Improved pseudorandom generators from pseudorandom multi-switching lemmas. In Approximation, randomization, and combinatorial optimization. Algorithms and techniques, volume 145 of LIPIcs, 2019. URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2019.45.
  35. Rocco A. Servedio and Li-Yang Tan. Pseudorandomness for read-k DNF formulas. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 621-638. SIAM, Philadelphia, PA, 2019. URL: https://doi.org/10.1137/1.9781611975482.39.
  36. Alexander A. Sherstov, Andrey A. Storozhenko, and Pei Wu. An Optimal Separation of Randomized and Quantum Query Complexity, 2020. URL: http://arxiv.org/abs/2008.10223.
  37. Roman Smolensky. Algebraic methods in the theory of lower bounds for boolean circuit complexity. In Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, STOC '87, page 77–82, New York, NY, USA, 1987. Association for Computing Machinery. URL: https://doi.org/10.1145/28395.28404.
  38. Avishay Tal. Tight bounds on the Fourier spectrum of AC⁰. In 32nd Computational Complexity Conference, volume 79 of LIPIcs, 2017. URL: https://doi.org/10.4230/LIPIcs.CCC.2017.15.
  39. Avishay Tal. Towards optimal separations between quantum and randomized query complexities. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 228-239, 2020. URL: https://doi.org/10.1109/FOCS46700.2020.00030.
  40. Emanuele Viola. On the power of small-depth computation. Foundations and Trends in Theoretical Computer Science, 5(1):1-72, 2009. Google Scholar
  41. Emanuele Viola. The sum of d small-bias generators fools polynomials of degree d. Comput. Complexity, 18(2):209-217, 2009. URL: https://doi.org/10.1007/s00037-009-0273-5.
  42. Emanuele Viola. Challenges in computational lower bounds. SIGACT News, Open Problems Column, 48(1), 2017. Google Scholar
  43. Emanuele Viola. Fourier conjectures, correlation bounds, and majority. Electron. Colloquium Comput. Complex., 27:175, 2020. URL: https://eccc.weizmann.ac.il/report/2020/175.
  44. Emanuele Viola. New lower bounds for probabilistic degree and AC0 with parity gates. Theory of Computing, 2021. Available at http://www.ccs.neu.edu/home/viola/. 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