Hitting Sets Give Two-Sided Derandomization of Small Space

by Kuan Cheng and William M. Hoza

Theory of Computing, Volume 18(21), pp. 1-32, 2022

Bibliography with links to cited articles

[1]   AmirMahdi Ahmadinejad, Jonathan Kelner, Jack Murtagh, John Peebles, Aaron Sidford, and Salil Vadhan: High-precision estimation of random walks in small space. In Proc. 61st FOCS, pp. 1295–1306. IEEE Comp. Soc., 2020. [doi:10.1109/FOCS46700.2020.00123, arXiv:1912.04524]

[2]   Miklós Ajtai, János Komlós, and Endre Szemerédi: Deterministic simulation in LOGSPACE. In Proc. 19th STOC, pp. 132–140. ACM Press, 1987. [doi:10.1145/28395.28410]

[3]   Alexander E. Andreev, Andrea E. F. Clementi, and José D. P. Rolim: A new general derandomization method. J. ACM, 45(1):179–213, 1998. Preliminary version in ICALP’96. [doi:10.1145/273865.273933]

[4]   Alexander E. Andreev, Andrea E. F. Clementi, José D. P. Rolim, and Luca Trevisan: Weak random sources, hitting sets, and BPP simulations. SIAM J. Comput., 28(6):2103–2116, 1999. Preliminary version in FOCS’97. [doi:10.1137/S0097539797325636, ECCC:TR97-011]

[5]   Roy Armoni: On the derandomization of space-bounded computations. In Proc. 2nd Internat. Workshop on Randomization and Computation (RANDOM’98), pp. 47–59. Springer, 1998. [doi:10.1007/3-540-49543-6_5]

[6]   Andrej Bogdanov: Pseudorandom generators for low degree polynomials. In Proc. 37th STOC, pp. 21–30. ACM Press, 2005. [doi:10.1145/1060590.1060594]

[7]   Andrej Bogdanov, Zeev Dvir, Elad Verbin, and Amir Yehudayoff: Pseudorandomness for width-2 branching programs. Theory of Computing, 9(7):283–292, 2013. [doi:10.4086/toc.2013.v009a007, ECCC:TR09-070]

[8]   Mark Braverman, Gil Cohen, and Sumegha Garg: Pseudorandom pseudo-distributions with near-optimal error for read-once branching programs. SIAM J. Comput., 49(5):242–299, 2020. Preliminary version in STOC’18. [doi:10.1137/18M1197734, ECCC:TR17-161]

[9]   Harry Buhrman and Lance Fortnow: One-sided versus two-sided error in probabilistic computation. In Proc. 16th Symp. Theoret. Aspects of Comp. Sci. (STACS’99), pp. 100–109. Springer, 1999. [doi:10.1007/3-540-49116-3_9]

[10]   Eshan Chattopadhyay and Jyun-Jie Liao: Optimal error pseudodistributions for read-once branching programs. In Proc. 35th Comput. Complexity Conf. (CCC’20), pp. 25:1–27. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2020. [doi:10.4230/LIPIcs.CCC.2020.25, arXiv:2002.07208, ECCC:TR20-069]

[11]   Kuan Cheng and William M. Hoza: Hitting sets give two-sided derandomization of small space. In Proc. 35th Comput. Complexity Conf. (CCC’20), pp. 10:1–25. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2020. [doi:10.4230/LIPIcs.CCC.2020.10, ECCC:TR20-016]

[12]   Gil Cohen, Dean Doron, Oren Renard, Ori Sberlo, and Amnon Ta-Shma: Error reduction for weighted PRGs against read once branching programs. In Proc. 36th Comput. Complexity Conf. (CCC’21), pp. 22:1–17. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2021. [doi:10.4230/LIPIcs.CCC.2021.22, ECCC:TR21-020]

[13]   Oded Goldreich, Salil Vadhan, and Avi Wigderson: Simplified derandomization of BPP using a hitting set generator. In Oded Goldreich, editor, Studies in Complexity and Cryptography, pp. 59–67. Springer, 2011. Preliminary version in RANDOM’99. [doi:10.1007/978-3-642-22670-0_8, ECCC:TR00-004]

[14]   Oded Goldreich and Avi Wigderson: Tiny families of functions with random properties: a quality-size trade-off for hashing. Random Struct. Algor., 11(4):315–343, 1997. Preliminary version in STOC’94. [doi:10.1002/(SICI)1098-2418(199712)11:4¡315::AID-RSA3¿3.3.CO;2-D, ECCC:TR94-002]

[15]   Parikshit Gopalan, Adam R. Klivans, and Raghu Meka: Learning functions of halfspaces using prefix covers. In Proc. 25th Ann. Conf. on Learning Theory (COLT’12), pp. 15.1–15.10. Springer, 2012. PMLR.

[16]   Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan, and Salil Vadhan: Better pseudorandom generators from milder pseudorandom restrictions. In Proc. 53rd FOCS, pp. 120–129. IEEE Comp. Soc., 2012. [doi:10.1109/FOCS.2012.77, arXiv:1210.0049, ECCC:TR12-123]

[17]   William M. Hoza: Better pseudodistributions and derandomization for space-bounded computation. In Proc. 25th Internat. Conf. on Randomization and Computation (RANDOM’21), pp. 28:1–23. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2021. [doi:10.4230/LIPIcs.APPROX/RANDOM.2021.28, ECCC:TR21-048]

[18]   William M. Hoza and Chris Umans: Targeted pseudorandom generators, simulation advice generators, and derandomizing logspace. SIAM J. Comput., 51(2):281–304, 2022. Preliminary version in STOC’17. [doi:10.1137/17M1145707, arXiv:1610.01199]

[19]   William M. Hoza and David Zuckerman: Simple optimal hitting sets for small-success RL. SIAM J. Comput., 49(4):811–820, 2020. Preliminary version in FOCS’18. [doi:10.1137/19M1268707, ECCC:TR18-063]

[20]   Russell Impagliazzo, Noam Nisan, and Avi Wigderson: Pseudorandomness for network algorithms. In Proc. 26th STOC, pp. 356–364. ACM Press, 1994. [doi:10.1145/195058.195190]

[21]   Russell Impagliazzo and Avi Wigderson: P = BPP if E requires exponential circuits: Derandomizing the XOR lemma. In Proc. 29th STOC, pp. 220–229. ACM Press, 1997. [doi:10.1145/258533.258590]

[22]   Richard E. Ladner and Nancy A. Lynch: Relativization of questions about log space computability. Math. Sys. Theory, 10(1):19–32, 1976. [doi:10.1007/BF01683260]

[23]   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. Preliminary version in STOC’93. [doi:10.1007/BF01200907]

[24]   Raghu Meka, Omer Reingold, and Avishay Tal: Pseudorandom generators for width-3 branching programs. In Proc. 51st STOC, pp. 626–637. ACM Press, 2019. [doi:10.1145/3313276.3316319, arXiv:1806.04256, ECCC:TR18-112]

[25]   Noam Nisan: Pseudorandom generators for space-bounded computation. Combinatorica, 12(4):449–461, 1992. Preliminary version in STOC’90. [doi:10.1007/BF01305237]

[26]   Noam Nisan: On read-once vs. multiple access to randomness in logspace. Theoret. Comput. Sci., 107(1):135–144, 1993. Preliminary version in SCT’90. [doi:10.1016/0304-3975(93)90258-U]

[27]   Noam Nisan and David Zuckerman: Randomness is linear in space. J. Comput. System Sci., 52(1):43–52, 1996. Preliminary version in STOC’93. [doi:10.1006/jcss.1996.0004]

[28]   Edward Pyne and Salil Vadhan: Pseudodistributions that beat all pseudorandom generators (extended abstract). In Proc. 36th Comput. Complexity Conf. (CCC’21), pp. 33:1–15. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2021. [doi:10.4230/LIPIcs.CCC.2021.33, ECCC:TR21-019]

[29]   Jiří Šíma and Stanislav Žák: A polynomial-time construction of a hitting set for read-once branching programs of width 3. Fundamenta Informaticae, 184(4):307–354, 2021. Preliminary versions in CSR’11 and SOFSEM’12. [doi:10.3233/fi-2021-2101, arXiv:2101.01151, ECCC:TR10-088]