Document Open Access Logo

Fourier Growth of Regular Branching Programs

Authors Chin Ho Lee, Edward Pyne, Salil Vadhan

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2022.2.pdf
  • Filesize: 0.81 MB
  • 21 pages

Document Identifiers

Author Details

Chin Ho Lee
  • Harvard University, Cambridge, MA, USA
Edward Pyne
  • Harvard University, Cambridge, MA, USA
Salil Vadhan
  • Harvard University, Cambridge, MA, USA

Funding

  • Lee, Chin Ho: Supported by NSF grant CCF-1763299 and a Simons Investigator grant to S. Vadhan.
  • Vadhan, Salil: Supported by NSF grant CCF-1763299 and a Simons Investigator grant.

Acknowledgements

We thank the anonymous reviewers for their helpful comments.

Cite As Get BibTex

Chin Ho Lee, Edward Pyne, and Salil Vadhan. Fourier Growth of Regular Branching Programs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 2:1-2:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2022.2

Abstract

We analyze the Fourier growth, i.e. the L₁ Fourier weight at level k (denoted L_{1,k}), of read-once regular branching programs. We prove that every read-once regular branching program B of width w ∈ [1,∞] with s accepting states on n-bit inputs must have its L_{1,k} bounded by min{Pr[B(U_n) = 1](w-1)^k, s ⋅ O((n log n)/k)^{(k-1)/2}}. For any constant k, our result is tight up to constant factors for the AND function on w-1 bits, and is tight up to polylogarithmic factors for unbounded width programs. In particular, for k = 1 we have L_{1,1}(B) ≤ s, with no dependence on the width w of the program.
Our result gives new bounds on the coin problem and new pseudorandom generators (PRGs). Furthermore, we obtain an explicit generator for unordered permutation branching programs of unbounded width with a constant factor stretch, where no PRG was previously known.
Applying a composition theorem of Błasiok, Ivanov, Jin, Lee, Servedio and Viola (RANDOM 2021), we extend our results to "generalized group products," a generalization of modular sums and product tests.

Subject Classification

ACM Subject Classification
  • Theory of computation → Pseudorandomness and derandomization
Keywords
  • pseudorandomness
  • fourier analysis

Metrics

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

Related Versions

References

  1. Scott Aaronson. BQP and the polynomial hierarchy. In STOC'10 - Proceedings of the 2010 ACM International Symposium on Theory of Computing, pages 141-150. ACM, New York, 2010. Google Scholar
  2. Scott Aaronson and Andrew Drucker. Advice coins for classical and quantum computation. In Automata, languages and programming. Part I, volume 6755 of Lecture Notes in Comput. Sci., pages 61-72. Springer, Heidelberg, 2011. URL: https://doi.org/10.1007/978-3-642-22006-7_6.
  3. Rohit Agrawal. Coin theorems and the Fourier expansion. Chic. J. Theoret. Comput. Sci., pages Art. 4, 15, 2020. URL: https://doi.org/10.4086/cjtcs.
  4. M. Ajtai. Σ^1_1-formulae on finite structures. Ann. Pure Appl. Logic, 24(1):1-48, 1983. URL: https://doi.org/10.1016/0168-0072(83)90038-6.
  5. 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.
  6. Nayantara Bhatnagar, Parikshit Gopalan, and Richard J. Lipton. Symmetric polynomials over z_m and simultaneous communication protocols. J. Comput. Syst. Sci., 72(2):252-285, 2006. URL: https://doi.org/10.1016/j.jcss.2005.06.007.
  7. 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.
  8. Jaroslaw Błasiok, Peter Ivanov, Yaonan Jin, Chin Ho Lee, Rocco A. Servedio, and Emanuele Viola. Fourier growth of structured F_2-polynomials and applications. In Mary Wootters and Laura Sanità, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2021, August 16-18, 2021, University of Washington, Seattle, Washington, USA (Virtual Conference), volume 207 of LIPIcs, pages 53:1-53:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2021.53.
  9. Andrej Bogdanov, William Hoza, Gautam Prakriya, and Edward Pyne. Hitting sets for regular branching programs. Electron. Colloquium Comput. Complex., page 143, 2021. URL: https://eccc.weizmann.ac.il/report/2021/143.
  10. Andrej Bogdanov, Periklis A. Papakonstantinou, and Andrew Wan. Pseudorandomness for read-once formulas. In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science - FOCS 2011, pages 240-246. IEEE Computer Soc., Los Alamitos, CA, 2011. URL: https://doi.org/10.1109/FOCS.2011.57.
  11. Mark Braverman, Sumegha Garg, and David P. Woodruff. The coin problem with applications to data streams. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science, pages 318-329. IEEE Computer Soc., Los Alamitos, CA, [2020] © 2020. Google Scholar
  12. Mark Braverman, Sumegha Garg, and Or Zamir. Tight space complexity of the coin problem. Electron. Colloquium Comput. Complex., page 83, 2021. URL: https://eccc.weizmann.ac.il/report/2021/083.
  13. Mark Braverman, Anup Rao, Ran Raz, and Amir Yehudayoff. Pseudorandom generators for regular branching programs. SIAM J. Comput., 43(3):973-986, 2014. URL: https://doi.org/10.1137/120875673.
  14. Joshua Brody and Elad Verbin. The coin problem, and pseudorandomness for branching programs. In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science - FOCS 2010, pages 30-39. IEEE Computer Soc., Los Alamitos, CA, 2010. Google Scholar
  15. Eshan Chattopadhyay, Jason Gaitonde, Chin Ho Lee, Shachar Lovett, and Abhishek Shetty. Fractional Pseudorandom Generators from Any Fourier Level. In Valentine Kabanets, editor, 36th Computational Complexity Conference (CCC 2021), volume 200 of Leibniz International Proceedings in Informatics (LIPIcs), pages 10:1-10:24, 2021. URL: https://doi.org/10.4230/LIPIcs.CCC.2021.10.
  16. 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.
  17. Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, Shachar Lovett, and David Zuckerman. XOR Lemmas for Resilient Functions against Polynomials. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, pages 234-246, New York, NY, USA, 2020. Association for Computing Machinery. URL: https://doi.org/10.1145/3357713.3384242.
  18. 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 Conference (ITCS 2019), volume 124 of Leibniz International Proceedings in Informatics (LIPIcs), pages 22:1-22:15. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.ITCS.2019.22.
  19. 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.
  20. Gil Cohen, Ivan Bjerre Damgård, Yuval Ishai, Jonas Kölker, Peter Bro Miltersen, Ran Raz, and Ron D. Rothblum. Efficient multiparty protocols via log-depth threshold formulae (extended abstract). In Advances in cryptology - CRYPTO 2013. Part II, volume 8043 of Lecture Notes in Comput. Sci., pages 185-202. Springer, Heidelberg, 2013. URL: https://doi.org/10.1007/978-3-642-40084-1_11.
  21. Anindya De. Pseudorandomness for permutation and regular branching programs. In 26th Annual IEEE Conference on Computational Complexity, pages 221-231. IEEE Computer Soc., Los Alamitos, CA, 2011. Google Scholar
  22. Dean Doron, Pooya Hatami, and William M. Hoza. Near-Optimal Pseudorandom Generators for Constant-Depth Read-Once Formulas. In 34th Computational Complexity Conference (CCC 2019), volume 137 of Leibniz International Proceedings in Informatics (LIPIcs), pages 16:1-16:34. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.CCC.2019.16.
  23. Dean Doron, Pooya Hatami, and William M. Hoza. Log-Seed Pseudorandom Generators via Iterated Restrictions. In 35th Computational Complexity Conference (CCC 2020), volume 169 of Leibniz International Proceedings in Informatics (LIPIcs), pages 6:1-6:36. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.CCC.2020.6.
  24. Dean Doron, Raghu Meka, Omer Reingold, Avishay Tal, and Salil Vadhan. Pseudorandom Generators for Read-Once Monotone Branching Programs. In Mary Wootters and Laura Sanità, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021), volume 207 of Leibniz International Proceedings in Informatics (LIPIcs), pages 58:1-58:21, 2021. URL: https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2021.58.
  25. Alexandros Eskenazis and Paata Ivanisvili. Learning low-degree functions from a logarithmic number of random queries. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 203-207, 2022. Google Scholar
  26. Michael A. Forbes and Zander Kelley. Pseudorandom generators for read-once branching programs, in any order. In 59th Annual IEEE Symposium on Foundations of Computer Science - FOCS 2018, pages 946-955. IEEE Computer Soc., Los Alamitos, CA, 2018. URL: https://doi.org/10.1109/FOCS.2018.00093.
  27. Uma Girish, Ran Raz, and Wei Zhan. Lower Bounds for XOR of Forrelations. In Mary Wootters and Laura Sanità, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021), volume 207 of Leibniz International Proceedings in Informatics (LIPIcs), pages 52:1-52:14, 2021. URL: https://drops.dagstuhl.de/opus/volltexte/2021/14745.
  28. Uma Girish, Avishay Tal, and Kewen Wu. Fourier Growth of Parity Decision Trees. In 36th Computational Complexity Conference (CCC 2021), volume 200 of Leibniz International Proceedings in Informatics (LIPIcs), pages 39:1-39:36. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.CCC.2021.39.
  29. Alexander Golovnev, Rahul Ilango, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, and Avishay Tal. AC⁰[p] Lower Bounds Against MCSP via the Coin Problem. In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), volume 132 of Leibniz International Proceedings in Informatics (LIPIcs), pages 66:1-66:15, 2019. URL: https://doi.org/10.4230/LIPIcs.ICALP.2019.66.
  30. Parikshit Gopalan, Daniel M. Kane, and Raghu Meka. Pseudorandomness via the discrete Fourier transform. SIAM J. Comput., 47(6):2451-2487, 2018. URL: https://doi.org/10.1137/16M1062132.
  31. Parikshit Gopalan, Raghu Meka, Omer Reingold, and David Zuckerman. Pseudorandom generators for combinatorial shapes. SIAM J. Comput., 42(3):1051-1076, 2013. URL: https://doi.org/10.1137/110854990.
  32. 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.
  33. Elad Haramaty, Chin Ho Lee, and Emanuele Viola. Bounded independence plus noise fools products. SIAM J. Comput., 47(2):493-523, 2018. URL: https://doi.org/10.1137/17M1129088.
  34. William M. Hoza, Edward Pyne, and Salil Vadhan. Pseudorandom Generators for Unbounded-Width Permutation Branching Programs. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021), volume 185 of Leibniz International Proceedings in Informatics (LIPIcs), pages 7:1-7:20. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.ITCS.2021.7.
  35. Russell Impagliazzo, Raghu Meka, and David Zuckerman. Pseudorandomness from shrinkage. J. ACM, 66(2):Art. 11, 16, 2019. URL: https://doi.org/10.1145/3230630.
  36. Siddharth Iyer, Anup Rao, Victor Reis, Thomas Rothvoss, and Amir Yehudayoff. Tight bounds on the fourier growth of bounded functions on the hypercube. CoRR, abs/2107.06309, 2021. URL: http://arxiv.org/abs/2107.06309.
  37. Chin Ho Lee. Fourier Bounds and Pseudorandom Generators for Product Tests. In 34th Computational Complexity Conference (CCC 2019), volume 137 of Leibniz International Proceedings in Informatics (LIPIcs), pages 7:1-7:25. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.CCC.2019.7.
  38. Chin Ho Lee and Emanuele Viola. The coin problem for product tests. ACM Trans. Comput. Theory, 10(3):Art. 14, 10, 2018. URL: https://doi.org/10.1145/3201787.
  39. 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.
  40. Nutan Limaye, Karteek Sreenivasaiah, Srikanth Srinivasan, Utkarsh Tripathi, and S. Venkitesh. A fixed-depth size-hierarchy theorem for AC⁰[⊕] via the coin problem. SIAM J. Comput., 50(4):1461-1499, 2021. URL: https://doi.org/10.1137/19M1276467.
  41. Shachar Lovett, Omer Reingold, Luca Trevisan, and Salil Vadhan. Pseudorandom bit generators that fool modular sums. In Approximation, randomization, and combinatorial optimization, volume 5687 of Lecture Notes in Comput. Sci., pages 615-630. Springer, Berlin, 2009. URL: https://doi.org/10.1007/978-3-642-03685-9_46.
  42. 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.
  43. 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.
  44. Raghu Meka and David Zuckerman. Small-bias spaces for group products. In Approximation, randomization, and combinatorial optimization, volume 5687 of Lecture Notes in Comput. Sci., pages 658-672. Springer, Berlin, 2009. URL: https://doi.org/10.1007/978-3-642-03685-9_49.
  45. Noam Nisan. Pseudorandom generators for space-bounded computation. Combinatorica, 12(4):449-461, 1992. URL: https://doi.org/10.1007/BF01305237.
  46. Ryan O'Donnell. Analysis of Boolean Functions. Cambridge University Press, 2014. URL: https://doi.org/10.1017/CBO9781139814782.
  47. 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.
  48. Edward Pyne and Salil Vadhan. Pseudodistributions That Beat All Pseudorandom Generators (Extended Abstract). In 36th Computational Complexity Conference (CCC 2021), volume 200 of Leibniz International Proceedings in Informatics (LIPIcs), pages 33:1-33:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.CCC.2021.33.
  49. Edward Pyne and Salil Vadhan. Deterministic approximation of random walks via queries in graphs of unbounded size. In Symposium on Simplicity in Algorithms (SOSA), pages 57-67. SIAM, 2022. Google Scholar
  50. 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.
  51. Omer Reingold, Thomas Steinke, and Salil Vadhan. Pseudorandomness for regular branching programs via Fourier analysis. In Approximation, randomization, and combinatorial optimization, volume 8096 of Lecture Notes in Comput. Sci., pages 655-670. Springer, Heidelberg, 2013. URL: https://doi.org/10.1007/978-3-642-40328-6_45.
  52. Omer Reingold, Luca Trevisan, and Salil Vadhan. Pseudorandom walks on regular digraphs and the RL vs. L problem. In STOC'06: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, pages 457-466. ACM, New York, 2006. URL: https://doi.org/10.1145/1132516.1132583.
  53. Ronen Shaltiel and Emanuele Viola. Hardness amplification proofs require majority. SIAM J. Comput., 39(7):3122-3154, 2010. URL: https://doi.org/10.1137/080735096.
  54. Alexander A. Sherstov, Andrey A. Storozhenko, and Pei Wu. An Optimal Separation of Randomized and Quantum Query Complexity, pages 1289-1302. Association for Computing Machinery, New York, NY, USA, 2021. URL: https://doi.org/10.1145/3406325.3451019.
  55. John Steinberger. The distinguishability of product distributions by read-once branching programs. In 2013 IEEE Conference on Computational Complexity - CCC 2013, pages 248-254. IEEE Computer Soc., Los Alamitos, CA, 2013. URL: https://doi.org/10.1109/CCC.2013.33.
  56. Thomas Steinke. Pseudorandomness for permutation branching programs without the group theory. Electron. Colloquium Comput. Complex., 2012. URL: http://eccc.hpi-web.de/report/2012/083.
  57. Thomas Steinke, Salil Vadhan, and Andrew Wan. Pseudorandomness and Fourier-growth bounds for width-3 branching programs. Theory Comput., 13:Paper No. 12, 50, 2017. URL: https://doi.org/10.4086/toc.2017.v013a012.
  58. Avishay Tal. Tight Bounds on the Fourier Spectrum of AC0. In 32nd Computational Complexity Conference (CCC 2017), volume 79 of Leibniz International Proceedings in Informatics (LIPIcs), pages 15:1-15:31. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017. URL: https://doi.org/10.4230/LIPIcs.CCC.2017.15.
  59. 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.
  60. L. G. Valiant. Short monotone formulae for the majority function. J. Algorithms, 5(3):363-366, 1984. URL: https://doi.org/10.1016/0196-6774(84)90016-6.
  61. Emanuele Viola. Fourier Conjectures, Correlation Bounds, and Majority. In Nikhil Bansal, Emanuela Merelli, and James Worrell, editors, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), volume 198 of Leibniz International Proceedings in Informatics (LIPIcs), pages 111:1-111:15, 2021. URL: https://doi.org/10.4230/LIPIcs.ICALP.2021.111.
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 About DROPS Imprint Privacy Contact