Document Open Access Logo

New PRGs for Unbounded-Width/Adaptive-Order Read-Once Branching Programs

Authors Lijie Chen , Xin Lyu, Avishay Tal, Hongxun Wu

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2023.39.pdf
  • Filesize: 0.83 MB
  • 20 pages

Document Identifiers

Author Details

Lijie Chen
  • Miller Institute for Basic Research in Science at University of California at Berkeley, CA, USA
Xin Lyu
  • University of California at Berkeley, CA, USA
Avishay Tal
  • University of California at Berkeley, CA, USA
Hongxun Wu
  • University of California at Berkeley, CA, USA

Funding

  • Chen, Lijie: Supported by a Miller Research Fellowship.
  • Tal, Avishay: Supported by a Sloan Research Fellowship and NSF CAREER Award CCF-2145474.

Cite As Get BibTex

Lijie Chen, Xin Lyu, Avishay Tal, and Hongxun Wu. New PRGs for Unbounded-Width/Adaptive-Order Read-Once Branching Programs. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 39:1-39:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.ICALP.2023.39

Abstract

We give the first pseudorandom generators with sub-linear seed length for the following variants of read-once branching programs (roBPs):  
1) First, we show there is an explicit PRG of seed length O(log²(n/ε)log(n)) fooling unbounded-width unordered permutation branching programs with a single accept state, where n is the length of the program. Previously, [Lee-Pyne-Vadhan RANDOM 2022] gave a PRG with seed length Ω(n) for this class. For the ordered case, [Hoza-Pyne-Vadhan ITCS 2021] gave a PRG with seed length Õ(log n ⋅ log 1/ε).
2) Second, we show there is an explicit PRG fooling unbounded-width unordered regular branching programs with a single accept state with seed length Õ(√{n ⋅ log 1/ε} + log 1/ε). Previously, no non-trivial PRG (with seed length less than n) was known for this class (even in the ordered setting). For the ordered case, [Bogdanov-Hoza-Prakriya-Pyne CCC 2022] gave an HSG with seed length Õ(log n ⋅ log 1/ε).
3) Third, we show there is an explicit PRG fooling width w adaptive branching programs with seed length O(log n ⋅ log² (nw/ε)). Here, the branching program can choose an input bit to read depending on its current state, while it is guaranteed that on any input x ∈ {0,1}ⁿ, the branching program reads each input bit exactly once. Previously, no PRG with a non-trivial seed length is known for this class. 
We remark that there are some functions computable by constant-width adaptive branching programs but not by sub-exponential-width unordered branching programs. 
In terms of techniques, we indeed show that the Forbes-Kelly PRG (with the right parameters) from [Forbes-Kelly FOCS 2018] already fools all variants of roBPs above. Our proof adds several new ideas to the original analysis of Forbes-Kelly, and we believe it further demonstrates the versatility of the Forbes-Kelly PRG.

Subject Classification

ACM Subject Classification
  • Theory of computation → Pseudorandomness and derandomization
Keywords
  • pseudorandom generators
  • derandomization
  • read-once branching programs

Metrics

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

References

  1. AmirMahdi Ahmadinejad, Jonathan A. Kelner, Jack Murtagh, John Peebles, Aaron Sidford, and Salil P. Vadhan. High-precision estimation of random walks in small space. In Sandy Irani, editor, 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 1295-1306. IEEE, 2020. Google Scholar
  2. Noga Alon, Oded Goldreich, Johan Håstad, and René Peralta. Simple constructions of almost k-wise independent random variables. Random Structures & Algorithms, 3(3):289-304, 1992. Google Scholar
  3. Andrej Bogdanov, William M. Hoza, Gautam Prakriya, and Edward Pyne. Hitting sets for regular branching programs. In Shachar Lovett, editor, 37th Computational Complexity Conference, CCC 2022, July 20-23, 2022, Philadelphia, PA, USA, volume 234 of LIPIcs, pages 3:1-3:22. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. Google Scholar
  4. Andrej Bogdanov, Periklis A. Papakonstantinou, and Andrew Wan. Pseudorandomness for read-once formulas. In Rafail Ostrovsky, editor, IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22-25, 2011, pages 240-246. IEEE Computer Society, 2011. Google Scholar
  5. Mark Braverman, Anup Rao, Ran Raz, and Amir Yehudayoff. Pseudorandom generators for regular branching programs. SIAM J. Comput., 43(3):973-986, 2014. Google Scholar
  6. Joshua Brody and Elad Verbin. The coin problem and pseudorandomness for branching programs. In 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA, pages 30-39. IEEE Computer Society, 2010. Google Scholar
  7. 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
  8. Michael A Forbes and Zander Kelley. Pseudorandom generators for read-once branching programs, in any order. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 946-955. IEEE, 2018. Google Scholar
  9. Anat Ganor and Ran Raz. Space pseudorandom generators by communication complexity lower bounds. In Klaus Jansen, José D. P. Rolim, Nikhil R. Devanur, and Cristopher Moore, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2014, September 4-6, 2014, Barcelona, Spain, volume 28 of LIPIcs, pages 692-703. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2014. Google Scholar
  10. Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan, and Salil Vadhan. Better pseudorandom generators from milder pseudorandom restrictions. In Proc. 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 120-129. IEEE, 2012. Google Scholar
  11. Elad Haramaty, Chin Ho Lee, and Emanuele Viola. Bounded independence plus noise fools products. SIAM J. Comput., 47(2):493-523, 2018. Google Scholar
  12. William M. Hoza, Edward Pyne, and Salil P. Vadhan. Pseudorandom generators for unbounded-width permutation branching programs. In James R. Lee, editor, 12th Innovations in Theoretical Computer Science Conference, ITCS 2021, January 6-8, 2021, Virtual Conference, volume 185 of LIPIcs, pages 7:1-7:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. Google Scholar
  13. Russell Impagliazzo, Valentine Kabanets, and Avi Wigderson. In search of an easy witness: exponential time vs. probabilistic polynomial time. Journal of Computer and System Sciences, 65(4):672-694, 2002. Google Scholar
  14. Russell Impagliazzo, Raghu Meka, and David Zuckerman. Pseudorandomness from shrinkage. In Proc. 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 111-119. IEEE, 2012. Google Scholar
  15. Russell Impagliazzo, Noam Nisan, and Avi Wigderson. Pseudorandomness for network algorithms. In Proc. 26th Annual ACM Symposium on Theory of Computing (STOC), pages 356-364, 1994. Google Scholar
  16. Russell Impagliazzo and Avi Wigderson. P = BPP if E requires exponential circuits: derandomizing the XOR lemma. In Proc. 29th Annual ACM Symposium on Theory of Computing (STOC), pages 220-229, 1997. Google Scholar
  17. Valentine Kabanets and Russell Impagliazzo. Derandomizing polynomial identity tests means proving circuit lower bounds. Computational Complexity, 13(1-2):1-46, 2004. Google Scholar
  18. Chin Ho Lee, Edward Pyne, and Salil P. Vadhan. Fourier growth of regular branching programs. In Amit Chakrabarti and Chaitanya Swamy, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2022, September 19-21, 2022, University of Illinois, Urbana-Champaign, USA (Virtual Conference), volume 245 of LIPIcs, pages 2:1-2:21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. Google Scholar
  19. Chin Ho Lee and Emanuele Viola. More on bounded independence plus noise: Pseudorandom generators for read-once polynomials. Theory of Computing, 16:1-50, 2020. Google Scholar
  20. Raghu Meka, Omer Reingold, and Avishay Tal. Pseudorandom generators for width-3 branching programs. In Moses Charikar and Edith Cohen, editors, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 626-637. ACM, 2019. Google Scholar
  21. Joseph Naor and Moni Naor. Small-bias probability spaces: efficient constructions and applications. SIAM Journal of Computing, 22(4):838-856, 1993. Google Scholar
  22. Noam Nisan. Pseudorandom generators for space-bounded computation. Combinatorica, 12(4):449-461, 1992. Google Scholar
  23. Noam Nisan and Avi Wigderson. Hardness vs. randomness. Journal of Computer and System Sciences, 49(2):149-167, 1994. Google Scholar
  24. Edward Pyne and Salil P. Vadhan. Limitations of the impagliazzo-nisan-wigderson pseudorandom generator against permutation branching programs. In Chi-Yeh Chen, Wing-Kai Hon, Ling-Ju Hung, and Chia-Wei Lee, editors, Computing and Combinatorics - 27th International Conference, COCOON 2021, Tainan, Taiwan, October 24-26, 2021, Proceedings, volume 13025 of Lecture Notes in Computer Science, pages 3-12. Springer, 2021. Google Scholar
  25. Edward Pyne and Salil P. Vadhan. Pseudodistributions that beat all pseudorandom generators (extended abstract). In Valentine Kabanets, editor, 36th Computational Complexity Conference, CCC 2021, July 20-23, 2021, Toronto, Ontario, Canada (Virtual Conference), volume 200 of LIPIcs, pages 33:1-33:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. Google Scholar
  26. Omer Reingold, Thomas Steinke, and Salil P. Vadhan. Pseudorandomness for regular branching programs via fourier analysis. In Prasad Raghavendra, Sofya Raskhodnikova, Klaus Jansen, and José D. P. Rolim, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 16th International Workshop, APPROX 2013, and 17th International Workshop, RANDOM 2013, Berkeley, CA, USA, August 21-23, 2013. Proceedings, volume 8096 of Lecture Notes in Computer Science, pages 655-670. Springer, 2013. Google Scholar
  27. Michael E. Saks and Shiyu Zhou. BP _hspace(s) subseteq dspace(s^3/2). Journal of Computer and System Sciences, 58(2):376-403, 1999. Google Scholar
  28. Thomas Steinke, Salil P. Vadhan, and Andrew Wan. Pseudorandomness and fourier-growth bounds for width-3 branching programs. Theory Comput., 13(1):1-50, 2017. Google Scholar
  29. Yoav Tzur. Notions of weak pseudorandomness and gf (2n)-polynomials. Master’s thesis, Weizmann Institute of Science, 2009. Google Scholar
  30. Salil P. Vadhan. Pseudorandomness. Foundations and Trends in Theoretical Computer Science. Now Publishers, 2012. 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 About DROPS Imprint Privacy Contact