Document Open Access Logo

Hitting Sets Give Two-Sided Derandomization of Small Space

Authors Kuan Cheng , William M. Hoza

PDF
Thumbnail PDF

File

LIPIcs.CCC.2020.10.pdf
  • Filesize: 0.61 MB
  • 25 pages

Document Identifiers

Author Details

Kuan Cheng
  • Department of Computer Science, University of Texas at Austin, TX, USA
William M. Hoza
  • Department of Computer Science, University of Texas at Austin, TX, USA

Funding

  • Cheng, Kuan: Supported by a Simons Investigator Award (#409864, David Zuckerman).
  • Hoza, William M.: Supported by the NSF GRFP under Grant DGE-1610403 and by a Harrington Fellowship from UT Austin.

Acknowledgements

We thank David Zuckerman, Dean Doron, and Pooya Hatami for helpful discussions and for comments on drafts of this paper. We thank Adam Klivans for bringing his work with Gopalan and Meka [Parikshit Gopalan et al., 2012] to our attention.

Cite As Get BibTex

Kuan Cheng and William M. Hoza. Hitting Sets Give Two-Sided Derandomization of Small Space. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 10:1-10:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.CCC.2020.10

Abstract

A hitting set is a "one-sided" variant of a pseudorandom generator (PRG), naturally suited to derandomizing algorithms that have one-sided error. We study the problem of using a given hitting set to derandomize algorithms that have two-sided error, focusing on space-bounded algorithms. For our first result, we show that if there is a log-space hitting set for polynomial-width read-once branching programs (ROBPs), then not only does 𝐋 = 𝐑𝐋, but 𝐋 = 𝐁𝐏𝐋 as well. This answers a question raised by Hoza and Zuckerman [William M. Hoza and David Zuckerman, 2018].
Next, we consider constant-width ROBPs. We show that if there are log-space hitting sets for constant-width ROBPs, then given black-box access to a constant-width ROBP f, it is possible to deterministically estimate 𝔼[f] to within ± ε in space O(log(n/ε)). Unconditionally, we give a deterministic algorithm for this problem with space complexity O(log² n + log(1/ε)), slightly improving over previous work.
Finally, we investigate the limits of this line of work. Perhaps the strongest reduction along these lines one could hope for would say that for every explicit hitting set, there is an explicit PRG with similar parameters. In the setting of constant-width ROBPs over a large alphabet, we prove that establishing such a strong reduction is at least as difficult as constructing a good PRG outright. Quantitatively, we prove that if the strong reduction holds, then for every constant α > 0, there is an explicit PRG for constant-width ROBPs with seed length O(log^{1 + α} n). Along the way, unconditionally, we construct an improved hitting set for ROBPs over a large alphabet.

Subject Classification

ACM Subject Classification
  • Theory of computation → Pseudorandomness and derandomization
  • Theory of computation → Complexity classes
Keywords
  • hitting sets
  • 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 Kelner, Jack Murtagh, John Peebles, Aaron Sidford, and Salil Vadhan. High-precision estimation of random walks in small space. arXiv preprint, 2019. URL: http://arxiv.org/abs/1912.04524.
  2. Miklós Ajtai, János Komlós, and Endre Szemerédi. Deterministic simulation in LOGSPACE. In Proceedings of the 19th Annual Symposium on Theory of Computing (STOC), pages 132-140. ACM, 1987. Google Scholar
  3. Alexander E. Andreev, Andrea E. F. Clementi, and José D. P. Rolim. Hitting sets derandomize BPP. In Automata, languages and programming (Paderborn, 1996), volume 1099 of Lecture Notes in Computer Science, pages 357-368. Springer, Berlin, 1996. URL: https://doi.org/10.1007/3-540-61440-0_142.
  4. Alexander E. Andreev, Andrea E. F. Clementi, José D. P. Rolim, and Luca Trevisan. Weak random sources, hitting sets, and BPP simulations. SIAM Journal on Computing, 28(6):2103-2116, 1999. URL: https://doi.org/10.1137/S0097539797325636.
  5. Roy Armoni. On the derandomization of space-bounded computations. In Proceedings of the 2nd International Workshop on Randomization and Computation (RANDOM), volume 1518 of Lecture Notes in Computer Science, pages 47-59. Springer, Berlin, 1998. URL: https://doi.org/10.1007/3-540-49543-6_5.
  6. Andrej Bogdanov. Pseudorandom generators for low degree polynomials. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC), pages 21-30, 2005. Google Scholar
  7. Andrej Bogdanov, Zeev Dvir, Elad Verbin, and Amir Yehudayoff. Pseudorandomness for width-2 branching programs. Theory of Computing, 9:283-292, 2013. URL: https://doi.org/10.4086/toc.2013.v009a007.
  8. Mark Braverman, Gil Cohen, and Sumegha Garg. Pseudorandom pseudo-distributions with near-optimal error for read-once branching programs. SIAM Journal on Computing, 0(0):STOC18-242-STOC18-299, 2020. URL: https://doi.org/10.1137/18M1197734.
  9. Harry Buhrman and Lance Fortnow. One-sided versus two-sided error in probabilistic computation. In Christoph Meinel and Sophie Tison, editors, Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science (STACS), pages 100-109, Berlin, Heidelberg, 1999. Springer Berlin Heidelberg. URL: https://doi.org/10.1007/3-540-49116-3_9.
  10. Eshan Chattopadhyay and Jyun-Jie Liao. Optimal error pseudodistributions for read-once branching programs. In Proceedings of the 35th Computational Complexity Conference (CCC), 2020. To appear. Google Scholar
  11. Oded Goldreich, Salil Vadhan, and Avi Wigderson. Simplified derandomization of BPP using a hitting set generator. In Studies in complexity and cryptography, volume 6650 of Lecture Notes in Computer Science, pages 59-67. Springer, Heidelberg, 2011. URL: https://doi.org/10.1007/978-3-642-22670-0_8.
  12. 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. URL: https://doi.org/10.1002/(SICI)1098-2418(199712)11:4<315::AID-RSA3>3.0.CO;2-1.
  13. Parikshit Gopalan, Adam R. Klivans, and Raghu Meka. Learning functions of halfspaces using prefix covers. In Shie Mannor, Nathan Srebro, and Robert C. Williamson, editors, Proceedings of the 25th Annual Conference on Learning Theory (COLT), volume 23 of Proceedings of Machine Learning Research, pages 15.1-15.10, Edinburgh, Scotland, 25-27 Jun 2012. PMLR. URL: http://proceedings.mlr.press/v23/gopalan12.html.
  14. Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan, and Salil Vadhan. Better pseudorandom generators from milder pseudorandom restrictions. In Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 120-129. IEEE, 2012. Google Scholar
  15. William M. Hoza and Chris Umans. Targeted pseudorandom generators, simulation advice generators, and derandomizing logspace. In Proceedings of the 49th Annual Symposium on Theory of Computing (STOC), pages 629-640. ACM, New York, 2017. Google Scholar
  16. William M. Hoza and David Zuckerman. Simple optimal hitting sets for small-success RL. In Proceedings of the 59th Annual IEEE Symposium on Foundations of Computer Science (FOCS). IEEE, 2018. Google Scholar
  17. Russell Impagliazzo, Noam Nisan, and Avi Wigderson. Pseudorandomness for network algorithms. In Proceedings of the 26th Annual ACM Symposium on Theory of Computing (STOC), pages 356-364. ACM, 1994. Google Scholar
  18. Russell Impagliazzo and Avi Wigderson. P = BPP if E requires exponential circuits: Derandomizing the XOR lemma. In Proceedings of the Twenty-ninth Annual ACM Symposium on Theory of Computing (STOC), pages 220-229, New York, NY, USA, 1997. ACM. Google Scholar
  19. Richard E. Ladner and Nancy A. Lynch. Relativization of questions about log space computability. Mathematical Systems Theory, 10(1):19-32, 1976. URL: https://doi.org/10.1007/BF01683260.
  20. Nathan Linial, Michael Luby, Michael Saks, and David Zuckerman. Efficient construction of a small hitting set for combinatorial rectangles in high dimension. Combinatorica, 17(2):215-234, 1997. URL: https://doi.org/10.1007/BF01200907.
  21. Raghu Meka, Omer Reingold, and Avishay Tal. Pseudorandom generators for width-3 branching programs. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 626-637. ACM, New York, 2019. Google Scholar
  22. Noam Nisan. Pseudorandom generators for space-bounded computation. Combinatorica, 12(4):449-461, 1992. URL: https://doi.org/10.1007/BF01305237.
  23. Noam Nisan. On read-once vs. multiple access to randomness in logspace. Theoretical Computer Science, 107(1):135-144, 1993. URL: https://doi.org/10.1016/0304-3975(93)90258-U.
  24. Noam Nisan and David Zuckerman. Randomness is linear in space. Journal of Computer and System Sciences, 52(1):43-52, 1996. URL: https://doi.org/10.1006/jcss.1996.0004.
  25. Jiří Šíma and Stanislav Žák. Almost k-wise independent sets establish hitting sets for width-3 1-branching programs. In Computer science - theory and applications, volume 6651 of Lecture Notes in Computer Science, pages 120-133. Springer, Heidelberg, 2011. URL: https://doi.org/10.1007/978-3-642-20712-9_10.
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