Document Open Access Logo

Improved Pseudorandom Generators for AC⁰ Circuits

Author Xin Lyu

PDF

File

Thumbnail PDF
PDF
LIPIcs.CCC.2022.34.pdf
  • Filesize: 0.88 MB
  • 25 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational complexity and cryptography
Keywords
  • pseudorandom generators
  • derandomization
  • switching Lemmas
  • AC⁰

Metrics

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

Abstract

We give PRG for depth-d, size-m AC⁰ circuits with seed length O(log^{d-1}(m)log(m/ε)log log(m)). Our PRG improves on previous work [Luca Trevisan and Tongke Xue, 2013; Rocco A. Servedio and Li-Yang Tan, 2019; Zander Kelley, 2021] from various aspects. It has optimal dependence on 1/ε and is only one "log log(m)" away from the lower bound barrier. For the case of d = 2, the seed length tightly matches the best-known PRG for CNFs [Anindya De et al., 2010; Avishay Tal, 2017].
There are two technical ingredients behind our new result; both of them might be of independent interest. First, we use a partitioning-based approach to construct PRGs based on restriction lemmas for AC⁰. Previous works [Luca Trevisan and Tongke Xue, 2013; Rocco A. Servedio and Li-Yang Tan, 2019; Zander Kelley, 2021] usually built PRGs on the Ajtai-Wigderson framework [Miklós Ajtai and Avi Wigderson, 1989]. Compared with them, the partitioning approach avoids the extra "log(n)" factor that usually arises from the Ajtai-Wigderson framework, allowing us to get the almost-tight seed length. The partitioning approach is quite general, and we believe it can help design PRGs for classes beyond constant-depth circuits.
Second, improving and extending [Luca Trevisan and Tongke Xue, 2013; Rocco A. Servedio and Li-Yang Tan, 2019; Zander Kelley, 2021], we prove a full derandomization of the powerful multi-switching lemma [Johan Håstad, 2014]. We show that one can use a short random seed to sample a restriction, such that a family of DNFs simultaneously simplifies under the restriction with high probability. This answers an open question in [Zander Kelley, 2021]. Previous derandomizations were either partial (that is, they pseudorandomly choose variables to restrict, and then fix those variables to truly-random bits) or had sub-optimal seed length. In our application, having a fully-derandomized switching lemma is crucial, and the randomness-efficiency of our derandomization allows us to get an almost-tight seed length.

Cite As Get BibTex

Xin Lyu. Improved Pseudorandom Generators for AC⁰ Circuits. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 34:1-34:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.CCC.2022.34

Author Details

Xin Lyu
  • Department of EECS, University of California at Berkeley, CA, USA

Acknowledgements

I would like to thank my advisor, Avishay Tal, for numerous insightful discussions during the project. I am grateful to Lijie Chen and Avishay Tal for helpful comments on an early draft, which helped me improve the presentation significantly. Finally, thank anonymous CCC reviewers for useful comments.

References

  1. Miklós Ajtai and Avi Wigderson. Deterministic simulation of probabilistic constant depth circuits. Adv. Comput. Res., 5:199-222, 1989. Google Scholar
  2. Paul Beame, Russell Impagliazzo, and Srikanth Srinivasan. Approximating AC^0 by small height decision trees and a deterministic algorithm for #AC^0SAT. In Computational Complexity Conference, pages 117-125. IEEE Computer Society, 2012. Google Scholar
  3. Mark Braverman. Polylogarithmic independence fools AC^0 circuits. J. ACM, 57(5):28:1-28:10, 2010. URL: https://doi.org/10.1145/1754399.1754401.
  4. Ruiwen Chen, Rahul Santhanam, and Srikanth Srinivasan. Average-case lower bounds and satisfiability algorithms for small threshold circuits. Theory Comput., 14(1):1-55, 2018. URL: https://doi.org/10.4086/toc.2018.v014a009.
  5. Anindya De, Omid Etesami, Luca Trevisan, and Madhur Tulsiani. Improved pseudorandom generators for depth 2 circuits. In Maria J. Serna, Ronen Shaltiel, Klaus Jansen, and José D. P. Rolim, editors, 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, pages 504-517. Springer, 2010. URL: https://doi.org/10.1007/978-3-642-15369-3_38.
  6. Dean Doron, Raghu Meka, Omer Reingold, Avishay Tal, and Salil P. Vadhan. Monotone branching programs: Pseudorandomness and circuit complexity. Electron. Colloquium Comput. Complex., page 18, 2021. URL: https://eccc.weizmann.ac.il/report/2021/018.
  7. Michael A. Forbes and Zander Kelley. Pseudorandom generators for read-once branching programs, in any order. In Mikkel Thorup, editor, 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 946-955. IEEE Computer Society, 2018. URL: https://doi.org/10.1109/FOCS.2018.00093.
  8. Oded Goldreich and Avi Wigderson. On the size of depth-three boolean circuits for computing multilinear functions. Electron. Colloquium Comput. Complex., page 43, 2013. URL: https://eccc.weizmann.ac.il/report/2013/043.
  9. Parikshit Gopalan, Raghu Meka, and Omer Reingold. DNF sparsification and a faster deterministic counting algorithm. Comput. Complex., 22(2):275-310, 2013. URL: https://doi.org/10.1007/s00037-013-0068-6.
  10. Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan, and Salil P. Vadhan. 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, pages 120-129. IEEE Computer Society, 2012. URL: https://doi.org/10.1109/FOCS.2012.77.
  11. Elad Haramaty, Chin Ho Lee, and Emanuele Viola. Bounded independence plus noise fools products. SIAM J. Comput., 47(2):493-523, 2018. URL: https://doi.org/10.1137/17M1129088.
  12. Prahladh Harsha and Srikanth Srinivasan. On polynomial approximations to AC. Random Struct. Algorithms, 54(2):289-303, 2019. URL: https://doi.org/10.1002/rsa.20786.
  13. Johan Håstad. On the correlation of parity and small-depth circuits. SIAM J. Comput., 43(5):1699-1708, 2014. URL: https://doi.org/10.1137/120897432.
  14. John Hastad. Almost optimal lower bounds for small depth circuits. Adv. Comput. Res., 5:143-170, 1989. Google Scholar
  15. Pooya Hatami, William Hoza, Avishay Tal, and Roei Tell. Fooling constant-depth threshold circuits. Electron. Colloquium Comput. Complex., page 2, 2021. URL: https://eccc.weizmann.ac.il/report/2021/002.
  16. Russell Impagliazzo, William Matthews, and Ramamohan Paturi. A satisfiability algorithm for ac^0. In SODA, pages 961-972. SIAM, 2012. Google Scholar
  17. Russell Impagliazzo, Raghu Meka, and David Zuckerman. Pseudorandomness from shrinkage. In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, pages 111-119. IEEE Computer Society, 2012. URL: https://doi.org/10.1109/FOCS.2012.78.
  18. Zander Kelley. An improved derandomization of the switching lemma. In Samir Khuller and Virginia Vassilevska Williams, editors, STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pages 272-282. ACM, 2021. URL: https://doi.org/10.1145/3406325.3451054.
  19. Chin Ho Lee and Emanuele Viola. More on bounded independence plus noise: Pseudorandom generators for read-once polynomials. Theory Comput., 16:1-50, 2020. URL: https://doi.org/10.4086/toc.2020.v016a007.
  20. Nathan Linial, Yishay Mansour, and Noam Nisan. Constant depth circuits, fourier transform, and learnability. J. ACM, 40(3):607-620, 1993. Google Scholar
  21. Michael Luby and Boban Velickovic. On deterministic approximation of DNF. Algorithmica, 16(4/5):415-433, 1996. URL: https://doi.org/10.1007/BF01940873.
  22. Raghu Meka, Omer Reingold, and Avishay Tal. Pseudorandom generators for width-3 branching programs. In Moses Charikar and Edith Cohen, editors, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 626-637. ACM, 2019. URL: https://doi.org/10.1145/3313276.3316319.
  23. Raghu Meka and David Zuckerman. Pseudorandom generators for polynomial threshold functions. SIAM J. Comput., 42(3):1275-1301, 2013. URL: https://doi.org/10.1137/100811623.
  24. Noam Nisan and Avi Wigderson. Hardness vs randomness. J. Comput. Syst. Sci., 49(2):149-167, 1994. URL: https://doi.org/10.1016/S0022-0000(05)80043-1.
  25. Rocco A. Servedio and Li-Yang Tan. Improved pseudorandom generators from pseudorandom multi-switching lemmas. In Dimitris Achlioptas and László A. Végh, editors, 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, pages 45:1-45:23. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2019.45.
  26. Avishay Tal. Tight bounds on the fourier spectrum of AC0. In Ryan O'Donnell, editor, 32nd Computational Complexity Conference, CCC 2017, July 6-9, 2017, Riga, Latvia, volume 79 of LIPIcs, pages 15:1-15:31. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. URL: https://doi.org/10.4230/LIPIcs.CCC.2017.15.
  27. Luca Trevisan and Tongke Xue. A derandomized switching lemma and an improved derandomization of AC0. In Proceedings of the 28th Conference on Computational Complexity, CCC 2013, K.lo Alto, California, USA, 5-7 June, 2013, pages 242-247. IEEE Computer Society, 2013. URL: https://doi.org/10.1109/CCC.2013.32.
  28. Salil P. Vadhan. Pseudorandomness. Found. Trends Theor. Comput. Sci., 7(1-3):1-336, 2012. URL: https://doi.org/10.1561/0400000010.
  29. Emanuele Viola. AC0 unpredictability. ACM Trans. Comput. Theory, 13(1):5:1-5:8, 2021. URL: https://doi.org/10.1145/3442362.
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