A Polynomial-Time Construction of a Hitting Set for Read-Once Branching Programs of Width 3

• Autorzy: Šíma Jiří , Žák Stanislav

Identyfikatory

DOI

10.3233/FI-2021-2101

• Języki publikacji: EN

Abstrakty

EN

Recently, an interest in constructing pseudorandom or hitting set generators for restricted branching programs has increased, which is motivated by the fundamental issue of derandomizing space-bounded computations. Such constructions have been known only in the case of width 2 and in very restricted cases of bounded width. In this paper, we characterize the hitting sets for read-once branching programs of width 3 by a so-called richness condition. Namely, we show that such sets hit the class of read-once conjunctions of DNF and CNF (i.e. the weak richness). Moreover, we prove that any rich set extended with all strings within Hamming distance of 3 is a hitting set for read-once branching programs of width 3. Then, we show that any almost O(log n)-wise independent set satisfies the richness condition. By using such a set due to Alon et al. (1992) our result provides an explicit polynomial-time construction of a hitting set for read-once branching programs of width 3 with acceptance probability ɛ > 5/6. We announced this result at conferences more than ten years ago, including only proof sketches, which motivated a number of subsequent results on pseudorandom generators for restricted read-once branching programs. This paper contains our original detailed proof that has not been published yet.

Słowa kluczowe

EN

derandomization; hitting set; read-once branching program; bounded width; almost k-wise independent set

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2021
• Tom: Vol. 184, nr 4
• Strony: 307--354
• Opis fizyczny: Bibliogr. 37 poz., rys., tab.

Twórcy

autor

Šíma Jiří

• Institute of Computer Science of the Czech Academy of Sciences, Prague, Czech Republic.

autor

Žák Stanislav

• Institute of Computer Science of the Czech Academy of Sciences, Prague, Czech Republic.

Bibliografia

• [1] Goldreich O, Wigderson A. Improved Derandomization of BPP Using a Hitting Set Generator. In: Hochbaum DS, Jansen K, Rolim JDP, Sinclair A (eds.), Randomization, Approximation, and Combinatorial Algorithms and Techniques, Third International Workshop on Randomization and Approximation Techniques in Computer Science, and Second International Workshop on Approximation Algorithms for Combinatorial Optimization Problems RANDOM-APPROX’99, Berkeley, CA, USA, August 8-11, 1999, Proceedings, volume 1671 of Lecture Notes in Computer Science. Springer, 1999 pp. 131-137. doi:10.1007/978-3-540-48413-4\_14.
• [2] Nisan N, Wigderson A. Hardness vs Randomness. J. Comput. Syst. Sci., 1994. 49(2):149-167. doi:10.1016/S0022-0000(05)80043-1.
• [3] Wegener I. Branching Programs and Binary Decision Diagrams. SIAM, 2000. ISBN 0-89871-458-3.
• [4] Nisan N. Pseudorandom generators for space-bounded computation. Comb., 1992. 12(4):449-461. doi:10.1007/BF01305237
• [5] Meka R, Zuckerman D. Pseudorandom Generators for Polynomial Threshold Functions. SIAM J. Comput., 2013. 42(3):1275-1301. doi:10.1137/100811623.
• [6] Vadhan SP. Pseudorandomness. Found. Trends Theor. Comput. Sci., 2012. 7(1-3):1-336. doi:10.1561/0400000010.
• [7] Bogdanov A, Dvir Z, Verbin E, Yehudayoff A. Pseudorandomness for Width-2 Branching Programs. Theory Comput., 2013. 9:283-293. doi:10.4086/toc.2013.v009a007.
• [8] Brody J, Verbin E. 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. IEEE Computer Society, 2010 pp. 30-39. doi:10.1109/FOCS.2010.10.
• [9] De A. Pseudorandomness for Permutation and Regular Branching Programs. In: Proceedings of the 26th Annual IEEE Conference on Computational Complexity, CCC 2011, San Jose, California, USA, June 8-10, 2011. IEEE Computer Society, 2011 pp. 221-231. doi:10.1109/CCC.2011.23.
• [10] Fefferman B, Shaltiel R, Umans C, Viola E. On Beating the Hybrid Argument. Theory Comput., 2013. 9:809-843. doi:10.4086/toc.2013.v009a026.
• [11] Beame P, Machmouchi W. Making Branching Programs Oblivious Requires Super logarithmic Overhead. In: Proceedings of the 26th Annual IEEE Conference on Computational Complexity, CCC 2011, San Jose, California, USA, June 8-10, 2011. IEEE Computer Society, 2011 pp. 12-22. doi:10.1109/CCC.2011.35.
• [12] Braverman M, Rao A, Raz R, Yehudayoff A. Pseudorandom Generators for Regular Branching Programs. SIAM J. Comput., 2014. 43(3):973-986. doi:10.1137/120875673.
• [13] Koucký M, Nimbhorkar P, Pudl´ak P. Pseudorandom generators for group products: extended abstract. In: Fortnow L, Vadhan SP (eds.), Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6-8 June 2011. ACM, 2011 pp. 263-272. doi:10.1145/1993636.1993672.
• [14] Šíma J, Žák S. A Polynomial Time Constructible Hitting Set for Restricted 1-Branching Programs of Width 3. In: van Leeuwen J, Italiano GF, van der Hoek W, Meinel C, Sack H, Plasil F (eds.), SOFSEM 2007: Theory and Practice of Computer Science, 33rd Conference on Current Trends in Theory and Practice of Computer Science, Harrachov, Czech Republic, January 20-26, 2007, Proceedings, volume 4362 of Lecture Notes in Computer Science. Springer, 2007 pp. 522-531. doi:10.1007/978-3-540-69507-3\_45.
• [15] De A, Etesami O, Trevisan L, Tulsiani M. Improved Pseudorandom Generators for Depth 2 Circuits. In:Serna MJ, Shaltiel R, Jansen K, Rolim JDP (eds.), Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 13th International Workshop, APPROX 2010, and 14th International Workshop, RANDOM 2010, Barcelona, Spain, September 1-3, 2010. Proceedings, volume 6302 of Lecture Notes in Computer Science. Springer, 2010 pp. 504-517. doi:10.1007/978-3-642-15369-3\_38.
• [16] Šíma J, Žák S. A Polynomial Time Construction of a Hitting Set for Read-Once Branching Programs of Width 3. Electron. Colloquium Comput. Complex., 2010. 17(TR10-088). URL https://eccc.weizmann.ac.il/report/2010/088.
• [17] Alon N, Goldreich O, H˚astad J, Peralta R. Simple Construction of Almost k-wise Independent Random Variables. Random Struct. Algorithms, 1992. 3(3):289-304. doi:10.1002/rsa.3240030308.
• [18] Šíma J, Žák S. A Sufficient Condition for Sets Hitting the Class of Read-Once Branching Programs of Width 3 - (Extended Abstract). In: Bielikov´a M, Friedrich G, Gottlob G, Katzenbeisser S, Tur´an G (eds.), SOFSEM 2012: Theory and Practice of Computer Science - 38th Conference on Current Trends in Theory and Practice of Computer Science, ˇSpindler˚uv Ml´yn, Czech Republic, January 21-27, 2012. Proceedings, volume 7147 of Lecture Notes in Computer Science. Springer, 2012 pp. 406-418. doi: 10.1007/978-3-642-27660-6\_33.
• [19] Šíma J, Žák S. Almost k-Wise Independent Sets Establish Hitting Sets for Width-3 1-Branching Programs. In: Kulikov AS, Vereshchagin NK (eds.), Computer Science - Theory and Applications - 6th International Computer Science Symposium in Russia, CSR 2011, St. Petersburg, Russia, June 14-18, 2011. Proceedings, volume 6651 of Lecture Notes in Computer Science. Springer, 2011 pp. 120-133. doi:10.1007/978-3-642-20712-9\_10.
• [20] Gopalan P, Meka R, Reingold O, Trevisan L, Vadhan SP. Better Pseudorandom Generators from Milder Pseudorandom Restrictions. In: 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012. IEEE Computer Society, 2012 pp. 120-129. doi:10.1109/FOCS.2012.77.
• [21] Steinke T. Pseudorandomness for Permutation Branching Programs Without the Group Theory. Electron. Colloquium Comput. Complex., 2012. 19:83. URL http://eccc.hpi-web.de/report/2012/083.
• [22] Forbes MA, Shpilka A. Quasipolynomial-Time Identity Testing of Non-commutative and Read-Once Oblivious Algebraic Branching Programs. In: 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA. IEEE Computer Society, 2013 pp. 243-252. doi:10.1109/FOCS.2013.34.
• [23] Reingold O, Steinke T, Vadhan SP. Pseudorandomness for Regular Branching Programs via Fourier Analysis. In: Raghavendra P, Raskhodnikova S, Jansen K, Rolim JDP (eds.), 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. Springer, 2013 pp. 655-670. doi:10.1007/978-3-642-40328-6\_45.
• [24] Steinberger JP. The Distinguishability of Product Distributions by Read-Once Branching Programs. In:Proceedings of the 28th Conference on Computational Complexity, CCC 2013, K.lo Alto, California, USA, 5-7 June, 2013. IEEE Computer Society, 2013 pp. 248-254. doi:10.1109/CCC.2013.33.
• [25] Watson T. Pseudorandom generators for combinatorial checkerboards. Comput. Complex., 2013. 22(4):727-769. doi:10.1007/s00037-012-0036-6.
• [26] Forbes MA, Saptharishi R, Shpilka A. Hitting sets for multilinear read-once algebraic branching programs, in any order. In: Shmoys DB (ed.), Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014. ACM, 2014 pp. 867-875. doi:10.1145/2591796.2591816.
• [27] Bazzi L, Nahas N. Small-Bias is Not Enough to Hit Read-Once CNF. Theory Comput. Syst., 2017. 60(2):324-345. doi:10.1007/s00224-016-9680-6.
• [28] Murtagh J, Reingold O, Sidford A, Vadhan SP. Derandomization Beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space. In: Umans C (ed.), 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017. IEEE Computer Society, 2017 pp. 801-812. doi:10.1109/FOCS.2017.79.
• [29] Servedio RA, Tan L. Deterministic Search for CNF Satisfying Assignments in Almost Polynomial Time. In: Umans C (ed.), 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017. IEEE Computer Society, 2017 pp. 813-823. doi:10.1109/FOCS.2017.80.
• [30] Steinke T, Vadhan SP, Wan A. Pseudorandomness and Fourier-Growth Bounds for Width-3 Branching Programs. Theory Comput., 2017. 13(1):1-50. doi:10.4086/toc.2017.v013a012. 354 J. Šíma and S. Žák / A Hitting Set for Width-3 1-Branching Programs [31] Ahmadinejad A, Kelner JA, Murtagh J, Peebles J, Sidford A, Vadhan SP. High-precision Estimation of Random Walks in Small Space. CoRR, 2019. abs/1912.04524. 1912.04524, URL http://arxiv.org/abs/1912.04524.
• [32] Doron D, Hatami P, Hoza WM. Near-Optimal Pseudorandom Generators for Constant-Depth Read-Once Formulas. In: Shpilka A (ed.), 34th Computational Complexity Conference, CCC 2019, July 18-20, 2019, New Brunswick, NJ, USA, volume 137 of LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019 pp. 16:1-16:34. doi:10.4230/LIPIcs.CCC.2019.16.
• [33] Meka R, Reingold O, Tal A. Pseudorandom generators for width-3 branching programs. In: Charikar M, Cohen E (eds.), Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019. ACM, 2019 pp. 626-637. doi:10.1145/3313276.3316319.
• [34] Servedio RA, Tan L. Improved Pseudorandom Generators from Pseudorandom Multi-Switching Lemmas. In: Achlioptas D, V´egh LA (eds.), Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2019, September 20-22, 2019, Massachusetts Institute of Technology, Cambridge, MA, USA, volume 145 of LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019 pp. 45:1-45:23. doi:10.4230/LIPIcs.APPROX-RANDOM.2019.45.
• [35] Braverman M, Cohen G, Garg S. Pseudorandom Pseudo-distributions with Near-Optimal Error for Read-Once Branching Programs. SIAM J. Comput., 2020. 49(5). doi:10.1137/18M1197734.
• [36] Cheng K, Hoza WM. Hitting Sets Give Two-Sided Derandomization of Small Space. In: Saraf S (ed.), 35th Computational Complexity Conference, CCC 2020, July 28-31, 2020, Saarbrücken, Germany (Virtual Conference), volume 169 of LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020 pp. 10:1-10:25. doi:10.4230/LIPIcs.CCC.2020.10.
• [37] Hoza WM, Zuckerman D. Simple Optimal Hitting Sets for Small-Success RL. SIAM J. Comput., 2020. 49(4):811-820. doi:10.1137/19M1268707.

Uwagi

Opracowanie rekordu ze środków MEiN, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2022-2023). (PL)