Document Open Access Logo

Tight Correlation Bounds for Circuits Between AC0 and TC0

Author Vinayak M. Kumar

PDF
Thumbnail PDF

File

LIPIcs.CCC.2023.18.pdf
  • Filesize: 1.03 MB
  • 40 pages

Document Identifiers

Author Details

Vinayak M. Kumar
  • Department of Computer Science, University of Texas at Austin, TX, USA

Funding

  • Kumar, Vinayak M.: Supported by NSF Grant CCF-2008076 and a Simons Investigator Award (#409864, David Zuckerman).

Acknowledgements

The author thanks David Zuckerman and Chin Ho Lee for many valuable discussions, Xin Lyu for explaining his work in [Lyu, 2022], anonymous reviewers for valuable feedback and for pointing us to the construction presented in Theorem 54, and Jeffrey Champion, Shivam Gupta, Michael Jaber and Jiawei Li for helpful comments.

Cite AsGet BibTex

Vinayak M. Kumar. Tight Correlation Bounds for Circuits Between AC0 and TC0. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 18:1-18:40, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.CCC.2023.18

Abstract

We initiate the study of generalized AC⁰ circuits comprised of arbitrary unbounded fan-in gates which only need to be constant over inputs of Hamming weight ≥ k (up to negations of the input bits), which we denote GC⁰(k). The gate set of this class includes biased LTFs like the k-OR (outputs 1 iff ≥ k bits are 1) and k-AND (outputs 0 iff ≥ k bits are 0), and thus can be seen as an interpolation between AC⁰ and TC⁰. We establish a tight multi-switching lemma for GC⁰(k) circuits, which bounds the probability that several depth-2 GC⁰(k) circuits do not simultaneously simplify under a random restriction. We also establish a new depth reduction lemma such that coupled with our multi-switching lemma, we can show many results obtained from the multi-switching lemma for depth-d size-s AC⁰ circuits lifts to depth-d size-s^{.99} GC⁰(.01 log s) circuits with no loss in parameters (other than hidden constants). Our result has the following applications: - Size-2^Ω(n^{1/d}) depth-d GC⁰(Ω(n^{1/d})) circuits do not correlate with parity (extending a result of Håstad (SICOMP, 2014)). - Size-n^Ω(log n) GC⁰(Ω(log² n)) circuits with n^{.249} arbitrary threshold gates or n^{.499} arbitrary symmetric gates exhibit exponentially small correlation against an explicit function (extending a result of Tan and Servedio (RANDOM, 2019)). - There is a seed length O((log m)^{d-1}log(m/ε)log log(m)) pseudorandom generator against size-m depth-d GC⁰(log m) circuits, matching the AC⁰ lower bound of Håstad up to a log log m factor (extending a result of Lyu (CCC, 2022)). - Size-m GC⁰(log m) circuits have exponentially small Fourier tails (extending a result of Tal (CCC, 2017)).

Subject Classification

ACM Subject Classification
  • Theory of computation → Circuit complexity
  • Theory of computation → Pseudorandomness and derandomization
Keywords
  • AC⁰
  • TC⁰
  • Switching Lemma
  • Lower Bounds
  • Correlation Bounds
  • Circuit Complexity

Metrics

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

Related Versions

References

  1. Scott Aaronson and Avi Wigderson. Algebrization: A new barrier in complexity theory. ACM Trans. Comput. Theory, 1(1), February 2009. URL: https://doi.org/10.1145/1490270.1490272.
  2. Eric Allender and Michal Koucký. Amplifying lower bounds by means of self-reducibility. J. ACM, 57(3), March 2010. URL: https://doi.org/10.1145/1706591.1706594.
  3. N. Alon, O. Goldreich, J. Hastad, and R. Peralta. Simple construction of almost k-wise independent random variables. In Proceedings [1990] 31st Annual Symposium on Foundations of Computer Science, pages 544-553 vol.2, 1990. URL: https://doi.org/10.1109/FSCS.1990.89575.
  4. Theodore Baker, John Gill, and Robert Solovay. Relativizations of the p?=np question. SIAM Journal on Computing, 4(4):431-442, 1975. URL: https://doi.org/10.1137/0204037.
  5. Norbert Blum. A boolean function requiring 3n network size. Theor. Comput. Sci., 28:337-345, 1984. URL: https://doi.org/10.1016/0304-3975(83)90029-4.
  6. Lijie Chen and Roei Tell. Bootstrapping results for threshold circuits “just beyond” known lower bounds. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, pages 34-41, New York, NY, USA, 2019. Association for Computing Machinery. URL: https://doi.org/10.1145/3313276.3316333.
  7. Johan Håstad. On the correlation of parity and small-depth circuits. SIAM Journal on Computing, 43(5):1699-1708, 2014. URL: https://doi.org/10.1137/120897432.
  8. Pooya Hatami, William M. Hoza, Avishay Tal, and Roei Tell. Fooling constant-depth threshold circuits (extended abstract). In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 104-115, 2022. URL: https://doi.org/10.1109/FOCS52979.2021.00019.
  9. Russell Impagliazzo, William Matthews, and Ramamohan Paturi. A satisfiability algorithm for ac0. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '12, pages 961-972, USA, 2012. Society for Industrial and Applied Mathematics. Google Scholar
  10. Russell Impagliazzo, Ramamohan Paturi, and Michael E. Saks. Size-depth tradeoffs for threshold circuits. SIAM Journal on Computing, 26(3):693-707, 1997. URL: https://doi.org/10.1137/S0097539792282965.
  11. Daniel M. Kane and Ryan Williams. Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits. In Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, STOC '16, pages 633-643, New York, NY, USA, 2016. Association for Computing Machinery. URL: https://doi.org/10.1145/2897518.2897636.
  12. 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.
  13. Eyal Kushilevitz and Yishay Mansour. Learning decision trees using the fourier spectrum. SIAM Journal on Computing, 22(6):1331-1348, 1993. URL: https://doi.org/10.1137/0222080.
  14. Eyal Kushilevitz and Noam Nisan. Communication Complexity. Cambridge University Press, 1996. URL: https://doi.org/10.1017/CBO9780511574948.
  15. Jiatu Li and Tianqi Yang. 3.1n − o(n) circuit lower bounds for explicit functions. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022, pages 1180-1193, New York, NY, USA, 2022. Association for Computing Machinery. URL: https://doi.org/10.1145/3519935.3519976.
  16. Nathan Linial, Yishay Mansour, and Noam Nisan. Constant depth circuits, fourier transform, and learnability. J. ACM, 40(3):607-620, July 1993. URL: https://doi.org/10.1145/174130.174138.
  17. Shachar Lovett and Srikanth Srinivasan. Correlation bounds for poly-size ac0 circuits with n(1-o(1)) symmetric gates. In Leslie Ann Goldberg, Klaus Jansen, R. Ravi, and José D. P. Rolim, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 640-651, Berlin, Heidelberg, 2011. Springer Berlin Heidelberg. Google Scholar
  18. Xin Lyu. Improved pseudorandom generators for ac0 circuits. In Proceedings of the 37th Computational Complexity Conference, CCC '22, Dagstuhl, DEU, 2022. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.CCC.2022.34.
  19. Yishay Mansour. An o(nlog log n) learning algorithm for dnf under the uniform distribution. In Proceedings of the Fifth Annual Workshop on Computational Learning Theory, COLT '92, pages 53-61, New York, NY, USA, 1992. Association for Computing Machinery. URL: https://doi.org/10.1145/130385.130391.
  20. Ryan O'Donnell. Analysis of Boolean Functions. Cambridge University Press, 2014. URL: https://doi.org/10.1017/CBO9781139814782.
  21. Igor Carboni Oliveira, Rahul Santhanam, and Srikanth Srinivasan. Parity Helps to Compute Majority. In Amir Shpilka, editor, 34th Computational Complexity Conference (CCC 2019), volume 137 of Leibniz International Proceedings in Informatics (LIPIcs), pages 23:1-23:17, Dagstuhl, Germany, 2019. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.CCC.2019.23.
  22. Aaron Potechin. On the approximation resistance of balanced linear threshold functions. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, pages 430-441, New York, NY, USA, 2019. Association for Computing Machinery. URL: https://doi.org/10.1145/3313276.3316374.
  23. Alexander Razborov and Avi Wigderson. n(log n) lower bounds on the size of depth-3 threshold cicuits with and gates at the bottom. Information Processing Letters, 45(6):303-307, 1993. URL: https://doi.org/10.1016/0020-0190(93)90041-7.
  24. Alexander A. Razborov. Lower bounds on the size of bounded depth circuits over a complete basis with logical addition. Mathematical notes of the Academy of Sciences of the USSR, 41:333-338, 1987. Google Scholar
  25. Alexander A Razborov and Steven Rudich. Natural proofs. Journal of Computer and System Sciences, 55(1):24-35, 1997. URL: https://doi.org/10.1006/jcss.1997.1494.
  26. Rocco A. Servedio. Every linear threshold function has a low-weight approximator. In Proceedings of the 21st Annual IEEE Conference on Computational Complexity, CCC '06, pages 18-32, USA, 2006. IEEE Computer Society. URL: https://doi.org/10.1109/CCC.2006.18.
  27. Rocco A. Servedio and Li-Yang Tan. Luby-Velickovic-Wigderson Revisited: Improved Correlation Bounds and Pseudorandom Generators for Depth-Two Circuits. In Eric Blais, Klaus Jansen, José D. P. Rolim, and David Steurer, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018), volume 116 of Leibniz International Proceedings in Informatics (LIPIcs), pages 56:1-56:20, Dagstuhl, Germany, 2018. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2018.56.
  28. Rocco A. Servedio and Li-Yang Tan. Improved pseudorandom generators from pseudorandom multi-switching lemmas. Theory of Computing, 18(4):1-46, 2022. URL: https://doi.org/10.4086/toc.2022.v018a004.
  29. R. Smolensky. Algebraic methods in the theory of lower bounds for boolean circuit complexity. In Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, STOC '87, pages 77-82, New York, NY, USA, 1987. Association for Computing Machinery. URL: https://doi.org/10.1145/28395.28404.
  30. Avishay Tal. Tight Bounds on the Fourier Spectrum of AC0. In Ryan O'Donnell, editor, 32nd Computational Complexity Conference (CCC 2017), volume 79 of Leibniz International Proceedings in Informatics (LIPIcs), pages 15:1-15:31, Dagstuhl, Germany, 2017. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.CCC.2017.15.
  31. Luca Trevisan and Tongke Xue. A derandomized switching lemma and an improved derandomization of ac0. In 2013 IEEE Conference on Computational Complexity, pages 242-247, 2013. URL: https://doi.org/10.1109/CCC.2013.32.
  32. Salil P. Vadhan. Pseudorandomness. Foundations and Trends® in Theoretical Computer Science, 7(1–3):1-336, 2012. URL: https://doi.org/10.1561/0400000010.
  33. Emanuele Viola. Pseudorandom bits for constant-depth circuits with few arbitrary symmetric gates. SIAM Journal on Computing, 36(5):1387-1403, 2007. URL: https://doi.org/10.1137/050640941.
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 Imprint Privacy Contact