Document Open Access Logo

Improved Pseudorandom Generators from Pseudorandom Multi-Switching Lemmas

Authors Rocco A. Servedio, Li-Yang Tan

PDF

File

Thumbnail PDF
PDF
LIPIcs.APPROX-RANDOM.2019.45.pdf
  • Filesize: 0.7 MB
  • 23 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Pseudorandomness and derandomization
Keywords
  • pseudorandom generators
  • switching lemmas
  • circuit complexity
  • unconditional derandomization

Metrics

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

Abstract

We give the best known pseudorandom generators for two touchstone classes in unconditional derandomization: small-depth circuits and sparse F_2 polynomials. Our main results are an epsilon-PRG for the class of size-M depth-d AC^0 circuits with seed length log(M)^{d+O(1)}* log(1/epsilon), and an epsilon-PRG for the class of S-sparse F_2 polynomials with seed length 2^{O(sqrt{log S})}* log(1/epsilon). These results bring the state of the art for unconditional derandomization of these classes into sharp alignment with the state of the art for computational hardness for all parameter settings: improving on the seed lengths of either PRG would require breakthrough progress on longstanding and notorious circuit lower bounds. 
The key enabling ingredient in our approach is a new pseudorandom multi-switching lemma. We derandomize recently-developed multi-switching lemmas, which are powerful generalizations of Håstad’s switching lemma that deal with families of depth-two circuits. Our pseudorandom multi-switching lemma - a randomness-efficient algorithm for sampling restrictions that simultaneously simplify all circuits in a family - achieves the parameters obtained by the (full randomness) multi-switching lemmas of Impagliazzo, Matthews, and Paturi [Impagliazzo et al., 2012] and Håstad [Johan Håstad, 2014]. This optimality of our derandomization translates into the optimality (given current circuit lower bounds) of our PRGs for AC^0 and sparse F_2 polynomials.

Cite As Get BibTex

Rocco A. Servedio and Li-Yang Tan. Improved Pseudorandom Generators from Pseudorandom Multi-Switching Lemmas. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 45:1-45:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2019.45

Author Details

Rocco A. Servedio
  • Department of Computer Science, Columbia University, New York, NY, USA
Li-Yang Tan
  • Department of Computer Science, Stanford University, Palo Alto, CA, USA

Funding

  • Servedio, Rocco A.: Supported by NSF grants CCF-1420349 and CCF-1563155.
  • Tan, Li-Yang: Supported by NSF grant CCF-1563122; part of this research was done during a visit to Columbia University.

Acknowledgements

We thank Prahladh Harsha and Srikanth Srinivasan for helpful discussions.

References

  1. Scott Aaronson. A Counterexample to the Generalized Linial-Nisan Conjecture. Electronic Colloquium on Computational Complexity, 17:109, 2010. Google Scholar
  2. Scott Aaronson. BQP and the polynomial hierarchy. In Proceedings of the 42nd ACM Symposium on Theory of Computing, pages 141-150, 2010. Google Scholar
  3. Manindra Agrawal, Eric Allender, Russell Impagliazzo, Toniann Pitassi, and Steven Rudich. Reducing the complexity of reductions. Comput. Complexity, 10(2):117-138, 2001. Google Scholar
  4. Miklós Ajtai. Σ₁¹-formulae on finite structures. Annals of Pure and Applied Logic, 24(1):1-48, 1983. Google Scholar
  5. Miklós Ajtai. Geometric properties of sets defined by constant depth circuits. In Combinatorics, Paul Erdős is eighty, Vol. 1, Bolyai Soc. Math. Stud., pages 19-31. János Bolyai Math. Soc., Budapest, 1993. Google Scholar
  6. Miklós Ajtai and Avi Wigderson. Deterministic Simulation of Probabilistic Constant Depth Circuits. In Proceedings of the 26th IEEE Symposium on Foundations of Computer Science (FOCS), pages 11-19, 1985. Google Scholar
  7. 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
  8. László Babai. Random oracles separate PSPACE from the polynomial-time hierarchy. Information Processing Letters, 26(1):51-53, 1987. Google Scholar
  9. László Babai, Noam Nisan, and Márió Szegedy. Multiparty protocols, pseudorandom generators for logspace, and time-space trade-offs. J. Comput. System Sci., 45(2):204-232, 1992. URL: https://doi.org/10.1016/0022-0000(92)90047-M.
  10. Marshall Ball, Dana Dachman-Soled, Siyao Guo, Tal Malkin, and Li-Yang Tan. Non-malleable codes for small-depth circuits. In Proceedings of the 59th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2018. To appear. Google Scholar
  11. Louay Bazzi. Polylogarithmic independence can fool DNF formulas. SIAM Journal on Computing, 38(6):2220-2272, 2009. Google Scholar
  12. Paul Beame. Lower bounds for recognizing small cliques on CRCW PRAM’s. Discrete Applied Mathematics, 29(1):3-20, 1990. Google Scholar
  13. Paul Beame, Russell Impagliazzo, and Srikanth Srinivasan. Approximating AC⁰ by Small Height Decision Trees and a Deterministic Algorithm for #AC⁰-SAT. In Proceedings of the 27th IEEE Conference on Computational Complexity (CCC), pages 117-125, 2012. Google Scholar
  14. Manuel Blum and Silvio Micali. How to Generate Cryptographically Strong Sequences of Pseudo Random Bits. In Proceedings of the 23rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 112-117, 1982. Google Scholar
  15. Andrej Bogdanov. Pseudorandom generators for low degree polynomials. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC), pages 21-30. SIAM, 2005. URL: https://doi.org/10.1145/1060590.1060594.
  16. Andrej Bogdanov and Emanuele Viola. Pseudorandom bits for polynomials. SIAM J. Comput., 39(6):2464-2486, 2010. URL: https://doi.org/10.1137/070712109.
  17. Jean Bourgain. Estimation of certain exponential sums arising in complexity theory. Comptes Rendus Mathematique, 340(9):627-631, 2005. URL: https://doi.org/10.1016/j.crma.2005.03.008.
  18. Mark Braverman. Polylogarithmic independence fools AC⁰ circuits. Journal of the ACM, 57(5):28, 2010. Google Scholar
  19. Jin-Yi Cai. With Probability One, a Random Oracle Separates PSPACE from the Polynomial-Time Hierarchy. In Proceedings of the 18th Annual ACM Symposium on Theory of Computing (STOC), pages 21-29, 1986. Google Scholar
  20. Arkadev Chattopadhyay. Discrepancy and the power of bottom fan-in in depth-three circuits. In Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 449-458, 2007. Google Scholar
  21. Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, and Shachar Lovett. Pseudorandom Generators from Polarizing Random Walks. In 33rd Computational Complexity Conference, CCC, pages 1:1-1:21, 2018. Google Scholar
  22. Eshan Chattopadhyay, Pooya Hatami, Shachar Lovett, and Avishay Tal. Pseudorandom Generators from the Second Fourier Level and Applications to AC⁰ with Parity Gates. In 10th Innovations in Theoretical Computer Science Conference (ITCS), pages 22:1-22:15, 2019. Google Scholar
  23. Eshan Chattopadhyay and Xin Li. Non-malleable codes and extractors for small-depth circuits, and affine functions. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 1171-1184. ACM, 2017. Google Scholar
  24. Shiva Chaudhuri and Jaikumar Radhakrishnan. Deterministic restrictions in circuit complexity. In Proceedings of the 28th Annual ACM Symposium on Theory of Computing (STOC), pages 30-36, 1996. Google Scholar
  25. Xi Chen, Igor Carboni Oliveira, Rocco A. Servedio, and Li-Yang Tan. Near-optimal small-depth lower bounds for small distance connectivity. In Proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC), pages 612-625, 2016. Google Scholar
  26. Anindya De, Omid Etesami, Luca Trevisan, and Madhur Tulsiani. Improved pseudorandom generators for depth 2 circuits. In Proceedings of the 13th International Workshop on Randomization and Computation (RANDOM), pages 504-517, 2010. Google Scholar
  27. Stefan Dziembowski, Krzysztof Pietrzak, and Daniel Wichs. Non-Malleable Codes. Journal of the ACM (JACM), 65(4):20, 2018. Google Scholar
  28. Bill Fefferman, Ronen Shaltiel, Christopher Umans, and Emanuele Viola. On beating the hybrid argument. In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference (ITCS), pages 468-483. ACM, 2012. Google Scholar
  29. Merrick Furst, James Saxe, and Michael Sipser. Parity, circuits, and the polynomial-time hierarchy. Mathematical Systems Theory, 17(1):13-27, 1984. Google Scholar
  30. Oded Goldreich and Avi Widgerson. On derandomizing algorithms that err extremely rarely. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC), pages 109-118, 2014. Google Scholar
  31. Parikshit Gopalan, Raghu Meka, and Omer Reingold. DNF sparsification and a faster deterministic counting algorithm. Comput. Complexity, 22(2):275-310, 2013. URL: https://doi.org/10.1007/s00037-013-0068-6.
  32. Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan, and Salil P. 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, 2012. Google Scholar
  33. Prahladh Harsha and Srikanth Srinivasan. On Polynomial Approximations to AC⁰. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2016, pages 32:1-32:14, 2016. Google Scholar
  34. Johan Håstad. Almost optimal lower bounds for small depth circuits. In Proceedings of the 18th Annual ACM Symposium on Theory of Computing (STOC), pages 6-20, 1986. Google Scholar
  35. Johan Håstad. On the Correlation of Parity and Small-Depth Circuits. SIAM Journal on Computing, 43(5):1699-1708, 2014. Google Scholar
  36. Johan Håstad. An Average-Case Depth Hierarchy Theorem for Higher Depths. In Proceedings of the 57th Annual Symposium on Foundations of Computer Science (FOCS), 2016. Google Scholar
  37. Johan Håstad. On small-depth Frege proofs for Tseitin for grids. In Proceedings of the 58th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 97-108. IEEE Computer Society, 2017. Google Scholar
  38. Johan Håstad and Mikael Goldmann. On the power of small-depth threshold circuits. Comput. Complexity, 1(2):113-129, 1991. URL: https://doi.org/10.1007/BF01272517.
  39. Russell Impagliazzo, William Matthews, and Ramamohan Paturi. A satisfiability algorithm for AC⁰. In Proceedings of the 23rd Annual Symposium on Discrete Algorithms (SODA), pages 961-972, 2012. Google Scholar
  40. Russell Impagliazzo, Raghu Meka, and David Zuckerman. Pseudorandomness from shrinkage. In Proceedings of the 53rd IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 111-119. IEEE Computer Society, 2012. Google Scholar
  41. Adam Klivans. On the Derandomization of Constant Depth Circuits. In Proceedings of 5th International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM), pages 249-260, 2001. Google Scholar
  42. Adam Klivans, Homin Lee, and Andrew Wan. Mansour’s Conjecture is True for Random DNF Formulas. In Proceedings of the 23rd Conference on Learning Theory (COLT), pages 368-380, 2010. Google Scholar
  43. Jan Krajíček, Pavel Pudlák, and Alan Woods. An exponential lower bound to the size of bounded depth Frege proofs of the pigeonhole principle. Random Structures & Algorithms, 7(1):15-39, 1995. Google Scholar
  44. Nathan Linial, Yishay Mansour, and Noam Nisan. Constant depth circuits, Fourier transform and learnability. Journal of the ACM, 40(3):607-620, 1993. Google Scholar
  45. Nathan Linial and Noam Nisan. Approximate inclusion-exclusion. Combinatorica, 10(4):349-365, 1990. Google Scholar
  46. Shachar Lovett. Unconditional pseudorandom generators for low-degree polynomials. Theory Comput., 5:69-82, 2009. URL: https://doi.org/10.4086/toc.2009.v005a003.
  47. Shachar Lovett and Srikanth Srinivasan. Correlation bounds for poly-size AC⁰ circuits with n^1-o(1) symmetric gates. In Approximation, randomization, and combinatorial optimization, volume 6845 of Lecture Notes in Comput. Sci., pages 640-651. Springer, Heidelberg, 2011. URL: https://doi.org/10.1007/978-3-642-22935-0_54.
  48. Chi-Jen Lu. Hitting set generators for sparse polynomials over any finite fields. In Proceedings of the 27th IEEE Conference on Computational Complexity (CCC), pages 280-286, 2012. URL: https://doi.org/10.1109/CCC.2012.20.
  49. Michael Luby and Boban Veličković. On deterministic approximation of DNF. Algorithmica, 16(4-5):415-433, 1996. URL: https://doi.org/10.1007/s004539900054.
  50. Michael Luby, Boban Veličković, and Avi Wigderson. Deterministic approximate counting of depth-2 circuits. In Proceedings of the 2nd ISTCS, pages 18-24, 1993. Google Scholar
  51. Joseph Naor and Moni Naor. Small-bias probability spaces: efficient constructions and applications. SIAM J. Comput., 22(4):838-856, 1993. URL: https://doi.org/10.1137/0222053.
  52. Noam Nisan. Pseudorandom bits for constant depth circuits. Combinatorica, 11(1):63-70, 1991. Google Scholar
  53. Noam Nisan and Avi Wigderson. Hardness vs. randomness. J. Comput. System Sci., 49(2):149-167, 1994. URL: https://doi.org/10.1016/S0022-0000(05)80043-1.
  54. Toniann Pitassi, Paul Beame, and Russell Impagliazzo. Exponential lower bounds for the pigeonhole principle. Computational complexity, 3(2):97-140, 1993. Google Scholar
  55. Toniann Pitassi, Benjamin Rossman, Rocco A. Servedio, and Li-Yang Tan. Poly-logarithmic Frege depth lower bounds via an expander switching lemma. In Proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC), pages 644-657, 2016. Google Scholar
  56. Alexander Razborov. A simple proof of Bazzi’s theorem. ACM Transactions on Computation Theory, 1(1):3, 2009. Google Scholar
  57. Benjamin Rossman. On the constant-depth complexity of k-clique. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC), pages 721-730, 2008. Google Scholar
  58. Benjamin Rossman. The Average Sensitivity of Bounded-Depth Formulas. In Proceedings of the 56th Annual Symposium on Foundations of Computer Science (FOCS), pages 424-430, 2015. Google Scholar
  59. Benjamin Rossman, Rocco A. Servedio, and Li-Yang Tan. An Average-Case Depth Hierarchy Theorem for Boolean Circuits. In Proceedings of the 56th Annual Symposium on Foundations of Computer Science (FOCS), pages 1030-1048, 2015. Google Scholar
  60. Rocco A. Servedio and Li-Yang Tan. What circuit classes can be learned with nontrivial savings? In Proceedings of the 8th Innovations in Theoretical Computer Science Conference (ITCS), 2017. Google Scholar
  61. Rocco A. Servedio and Li-Yang Tan. Luby-Veličković-Wigderson revisited: Improved correlation bounds and pseudorandom generators for depth-two circuits. In Proceedings of the 22nd International Workshop on Randomization and Computation (RANDOM), pages 56:1-56:20, 2018. Google Scholar
  62. Jirí Síma and Stanislav Zák. A Polynomial Time Construction of a Hitting Set for Read-Once Branching Programs of Width 3. Electronic Colloquium on Computational Complexity (ECCC), 17:88, 2010. Google Scholar
  63. Avishay Tal. Tight Bounds on the Fourier Spectrum of AC⁰. In Proceedings of the 32nd Computational Complexity Conference (CCC), pages 15:1-15:31, 2017. URL: https://doi.org/10.4230/LIPIcs.CCC.2017.15.
  64. Luca Trevisan. A note on approximate counting for k-DNF. In Proceedings of the 8th International Workshop on Randomization and Computation (RANDOM), pages 417-426, 2004. Google Scholar
  65. Luca Trevisan and Tongke Xue. A derandomized switching lemma and an improved derandomization of AC⁰ . In Proceedings of the 28th IEEE Conference on Computational Complexity (CCC), pages 242-247, 2013. Google Scholar
  66. Emanuele Viola. Pseudorandom bits for constant-depth circuits with few arbitrary symmetric gates. SIAM J. Comput., 36(5):1387-1403, 2007. URL: https://doi.org/10.1137/050640941.
  67. Emanuele Viola. On the power of small-depth computation. Now Publishers Inc, 2009. Google Scholar
  68. Emanuele Viola. The sum of d small-bias generators fools polynomials of degree d. Comput. Complexity, 18(2):209-217, 2009. URL: https://doi.org/10.1007/s00037-009-0273-5.
  69. Emanuele Viola and Avi Wigderson. Norms, XOR Lemmas, and Lower Bounds for Polynomials and Protocols. Theory of Computing, 4(7):137-168, 2008. URL: https://doi.org/10.4086/toc.2008.v004a007.
  70. Andrew Yao. Theory and applications of trapdoor functions. In Proceedings of the 23rd Annual Symposium on Foundations of Computer Science (FOCS), pages 80-91, 1982. Google Scholar
  71. Andrew Yao. Separating the polynomial-time hierarchy by oracles. In Proceedings of the 26th Annual Symposium on Foundations of Computer Science (FOCS), pages 1-10, 1985. Google Scholar
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact