Document Open Access Logo

Error Reduction for Weighted PRGs Against Read Once Branching Programs

Authors Gil Cohen, Dean Doron, Oren Renard, Ori Sberlo, Amnon Ta-Shma

PDF
Thumbnail PDF

File

LIPIcs.CCC.2021.22.pdf
  • Filesize: 0.72 MB
  • 17 pages

Document Identifiers

Author Details

Gil Cohen
  • School of Computer Science, Tel Aviv University, Israel
Dean Doron
  • Department of Computer Science, Stanford University, CA, USA
Oren Renard
  • School of Computer Science, Tel Aviv University, Israel
Ori Sberlo
  • School of Computer Science, Tel Aviv University, Israel
Amnon Ta-Shma
  • School of Computer Science, Tel Aviv University, Israel

Funding

  • Cohen, Gil: Supported by ERC starting grant 949499 and by Israel Science Foundation grant 1569/18.
  • Doron, Dean: Supported by NSF award CCF-1763311.
  • Renard, Oren: Supported by the Azrieli Faculty Fellowship.
  • Sberlo, Ori: Supported by ERC starting grant 949499 and by ISF grant 952/18.
  • Ta-Shma, Amnon: Supported by Israel Science Foundation grant 952/18.

Cite As Get BibTex

Gil Cohen, Dean Doron, Oren Renard, Ori Sberlo, and Amnon Ta-Shma. Error Reduction for Weighted PRGs Against Read Once Branching Programs. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 22:1-22:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.CCC.2021.22

Abstract

Weighted pseudorandom generators (WPRGs), introduced by Braverman, Cohen and Garg [Braverman et al., 2020], are a generalization of pseudorandom generators (PRGs) in which arbitrary real weights are considered, rather than a probability mass. Braverman et al. constructed WPRGs against read once branching programs (ROBPs) with near-optimal dependence on the error parameter. Chattopadhyay and Liao [Eshan Chattopadhyay and Jyun-Jie Liao, 2020] somewhat simplified the technically involved BCG construction, also obtaining some improvement in parameters.
In this work we devise an error reduction procedure for PRGs against ROBPs. More precisely, our procedure transforms any PRG against length n width w ROBP with error 1/poly(n) having seed length s to a WPRG with seed length s + O(logw/(ε) ⋅ log log1/(ε)). By instantiating our procedure with Nisan’s PRG [Noam Nisan, 1992] we obtain a WPRG with seed length O(log{n} ⋅ log(nw) + logw/(ε) ⋅ log log 1/(ε)). This improves upon [Braverman et al., 2020] and is incomparable with [Eshan Chattopadhyay and Jyun-Jie Liao, 2020].
Our construction is significantly simpler on the technical side and is conceptually cleaner. Another advantage of our construction is its low space complexity O(log{nw})+poly(log log1/(ε)) which is logarithmic in n for interesting values of the error parameter ε. Previous constructions (like [Braverman et al., 2020; Eshan Chattopadhyay and Jyun-Jie Liao, 2020]) specify the seed length but not the space complexity, though it is plausible they can also achieve such (or close) space complexity.

Subject Classification

ACM Subject Classification
  • Theory of computation → Pseudorandomness and derandomization
Keywords
  • Pseudorandom generators
  • Read once branching programs
  • Space-bounded computation

Metrics

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

References

  1. AmirMahdi Ahmadinejad, Jonathan Kelner, Jack Murtagh, John Peebles, Aaron Sidford, and Salil Vadhan. High-precision estimation of random walks in small space. In Proceedings of the 61st Annual IEEE Symposium on Foundations of Computer Science (FOCS 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. Sanjeev Arora and Boaz Barak. Computational Complexity - A Modern Approach. Cambridge University Press, 2009. URL: http://www.cambridge.org/catalogue/catalogue.asp?isbn=9780521424264.
  4. Allan Borodin, Stephen Cook, and Nicholas Pippenger. Parallel computation for well-endowed rings and space-bounded probabilistic machines. Information and Control, 58(1-3):113-136, 1983. Google Scholar
  5. Mark Braverman, Gil Cohen, and Sumegha Garg. Pseudorandom pseudo-distributions with near-optimal error for read-once branching programs. SIAM Journal on Computing, 49(5):STOC18-242-STOC18-299, 2020. Google Scholar
  6. Eshan Chattopadhyay and Jyun-Jie Liao. Optimal error pseudodistributions for read-once branching programs. In Proceedings of the 35th Computational Complexity Conference (CCC 2020). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020. Google Scholar
  7. Kuan Cheng and William M. Hoza. Hitting sets give two-sided derandomization of small space. In 35th Computational Complexity Conference (CCC 2020). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020. Google Scholar
  8. Michael B. Cohen, Jonathan Kelner, John Peebles, Richard Peng, Anup B. Rao, Aaron Sidford, and Adrian Vladu. Almost linear-time algorithms for Markov chains and new spectral primitives for directed graphs. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2017). ACM, 2017. Google Scholar
  9. Michael B. Cohen, Jonathan Kelner, John Peebles, Richard Peng, Aaron Sidford, and Adrian Vladu. Faster algorithms for computing the stationary distribution, simulating random walks, and more. In Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2016). IEEE, 2016. Google Scholar
  10. Oded Goldreich. Computational complexity: a conceptual perspective. Cambridge University Press, Cambridge, 2008. Google Scholar
  11. Oded Goldreich and Avi Wigderson. Tiny families of functions with random properties: A quality-size trade-off for hashing. Random Structures & Algorithms, 11(4):315-343, 1997. Google Scholar
  12. Alexander Healy and Emanuele Viola. Constant-depth circuits for arithmetic in finite fields of characteristic two. In Annual Symposium on Theoretical Aspects of Computer Science (STACS 2006). Springer, 2006. Google Scholar
  13. William M. Hoza and David Zuckerman. Simple optimal hitting sets for small-success RL. SIAM Journal on Computing, 49(4):811-820, 2020. Google Scholar
  14. Russel 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
  15. Russell Impagliazzo, Noam Nisan, and Avi Wigderson. Pseudorandomness for network algorithms. In Proceedings of the 26th Annual ACM SIGACT Symposium on Theory of Computing (STOC 1994). ACM, 1994. Google Scholar
  16. Valentine Kabanets and Russell Impagliazzo. Derandomizing polynomial identity tests means proving circuit lower bounds. computational complexity, 13(1-2):1-46, 2004. Google Scholar
  17. Noam Nisan. Pseudorandom generators for space-bounded computation. Combinatorica, 12(4):449-461, 1992. Google Scholar
  18. Noam Nisan. RL ⊆ SC. computational complexity, 4(1):1-11, 1994. Google Scholar
  19. Noam Nisan and Avi Wigderson. Hardness vs. randomness. Journal of Computer and System Sciences, 49(2):149-167, 1994. Google Scholar
  20. Edward Pyne and Salil Vadhan. personal communication, February 2021. Google Scholar
  21. Ran Raz and Omer Reingold. On recycling the randomness of states in space bounded computation. In Proceedings of the 31st Annual ACM SIGACT Symposium on Theory of Computing (STOC 1999). ACM, 1999. Google Scholar
  22. Michael E. Saks and Shiyu Zhou. BP_HSPACE(S) ⊆ DSPACE(S^2/3). Journal of Computer and System Sceinces, 58(2):376-403, 1999. Google Scholar
  23. Walter J. Savitch. Relationships between nondeterministic and deterministic tape complexities. Journal of Computer and System Sciences, 4(2):177-192, April 1970. 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