Document Open Access Logo

New Lower Bounds and Derandomization for ACC, and a Derandomization-Centric View on the Algorithmic Method

Author Lijie Chen

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2023.34.pdf
  • Filesize: 0.8 MB
  • 15 pages

Document Identifiers

Author Details

Lijie Chen
  • Miller Institute for Basic Research in Science at University of California, Berkeley, CA, USA

Acknowledgements

The author would like to thank Hanlin Ren, Roei Tell, Nikhil Vyas, and Ryan Williams for helpful discussions.

Cite As Get BibTex

Lijie Chen. New Lower Bounds and Derandomization for ACC, and a Derandomization-Centric View on the Algorithmic Method. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 34:1-34:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.ITCS.2023.34

Abstract

In this paper, we obtain several new results on lower bounds and derandomization for ACC⁰ circuits (constant-depth circuits consisting of AND/OR/MOD_m gates for a fixed constant m, a frontier class in circuit complexity):  
1) We prove that any polynomial-time Merlin-Arthur proof system with an ACC⁰ verifier (denoted by MA_{ACC⁰}) can be simulated by a nondeterministic proof system with quasi-polynomial running time and polynomial proof length, on infinitely many input lengths. This improves the previous simulation by [Chen, Lyu, and Williams, FOCS 2020], which requires both quasi-polynomial running time and proof length.
2) We show that MA_{ACC⁰} cannot be computed by fixed-polynomial-size ACC⁰ circuits, and our hard languages are hard on a sufficiently dense set of input lengths.
3) We show that NEXP (nondeterministic exponential-time) does not have ACC⁰ circuits of sub-half-exponential size, improving the previous sub-third-exponential size lower bound for NEXP against ACC⁰ by [Williams, J. ACM 2014].
Combining our first and second results gives a conceptually simpler and derandomization-centric proof of the recent breakthrough result NQP := NTIME[2^polylog(n)] ̸ ⊂ ACC⁰ by [Murray and Williams, SICOMP 2020]: Instead of going through an easy witness lemma as they did, we first prove an ACC⁰ lower bound for a subclass of MA, and then derandomize that subclass into NQP, while retaining its hardness against ACC⁰. 
Moreover, since our derandomization of MA_{ACC⁰} achieves a polynomial proof length, we indeed prove that nondeterministic quasi-polynomial-time with n^ω(1) nondeterminism bits (denoted as NTIMEGUESS[2^polylog(n), n^ω(1)]) has no poly(n)-size ACC⁰ circuits, giving a new proof of a result by Vyas. Combining with a win-win argument based on randomized encodings from [Chen and Ren, STOC 2020], we also prove that NTIMEGUESS[2^polylog(n), n^ω(1)] cannot be 1/2+1/poly(n)-approximated by poly(n)-size ACC⁰ circuits, improving the recent strongly average-case lower bounds for NQP against ACC⁰ by [Chen and Ren, STOC 2020].
One interesting technical ingredient behind our second result is the construction of a PSPACE-complete language that is paddable, downward self-reducible, same-length checkable, and weakly error correctable. Moreover, all its reducibility properties have corresponding AC⁰[2] non-adaptive oracle circuits. Our construction builds and improves upon similar constructions from [Trevisan and Vadhan, Complexity 2007] and [Chen, FOCS 2019], which all require at least TC⁰ oracle circuits for implementing these properties.

Subject Classification

ACM Subject Classification
  • Theory of computation → Circuit complexity
Keywords
  • Circuit Lower Bounds
  • Derandomization
  • Algorithmic Method
  • ACC

Metrics

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

Related Versions

References

  1. M. Ajtai. Σ^1_1-formulae on finite structures. Annals of Pure and Applied Logic, 24(1):1-48, 1983. Google Scholar
  2. Benny Applebaum, Yuval Ishai, and Eyal Kushilevitz. Cryptography in NC⁰. SIAM J. Comput., 36(4):845-888, 2006. URL: https://doi.org/10.1137/S0097539705446950.
  3. Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and the hardness of approximation problems. J. ACM, 45(3):501-555, 1998. URL: https://doi.org/10.1145/278298.278306.
  4. Sanjeev Arora and Shmuel Safra. Probabilistic checking of proofs: A new characterization of NP. J. ACM, 45(1):70-122, 1998. URL: https://doi.org/10.1145/273865.273901.
  5. Eli Ben-Sasson and Emanuele Viola. Short PCPs with projection queries. In Proc. 41st International Colloquium on Automata, Languages and Programming (ICALP), pages 163-173, 2014. Google Scholar
  6. Lijie Chen. Non-deterministic quasi-polynomial time is average-case hard for ACC circuits. In Proc. 60th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 1281-1304, 2019. Google Scholar
  7. Lijie Chen, Xin Lyu, and Richard Ryan Williams. Almost-everywhere circuit lower bounds from non-trivial derandomization. In Proc. 61st Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 1-12, 2020. Google Scholar
  8. Lijie Chen and Hanlin Ren. Strong average-case lower bounds from non-trivial derandomization. In Proc. 52nd Annual ACM Symposium on Theory of Computing (STOC), pages 1327-1334, 2020. Google Scholar
  9. Lijie Chen and Hanlin Ren. Strong average-case circuit lower bounds from nontrivial derandomization. SIAM Journal of Computing, 51(3):STOC20-115, 2021. Google Scholar
  10. Lijie Chen and R. Ryan Williams. Stronger Connections Between Circuit Analysis and Circuit Lower Bounds, via PCPs of Proximity. In çc34th, pages 19:1-19:43, 2019. Google Scholar
  11. Ruiwen Chen, Igor Carboni Oliveira, and Rahul Santhanam. An average-case lower bound against ACC⁰. In LATIN 2018: Theoretical Informatics - 13th Latin American Symposium, Proceedings, pages 317-330, 2018. Google Scholar
  12. Merrick Furst, James B. Saxe, and Michael Sipser. Parity, circuits, and the polynomial-time hierarchy. Mathematical Systems Theory, 17(1):13-27, 1984. Google Scholar
  13. Aryeh Grinberg, Ronen Shaltiel, and Emanuele Viola. Indistinguishability by adaptive procedures with advice, and lower bounds on hardness amplification proofs. In Proc. 59th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 956-966, 2018. Google Scholar
  14. Joshua A. Grochow and Toniann Pitassi. Circuit complexity, proof complexity, and polynomial identity testing: The ideal proof system. J. ACM, 65(6):37:1-37:59, 2018. URL: https://doi.org/10.1145/3230742.
  15. Johan Håstad. Almost optimal lower bounds for small depth circuits. Advances in Computing Research, 5:143-170, 1989. Google Scholar
  16. Alexander Healy and Emanuele Viola. Constant-depth circuits for arithmetic in finite fields of characteristic two. In Proc. 23rd Symposium on Theoretical Aspects of Computer Science (STACS), pages 672-683, 2006. Google Scholar
  17. William Hesse, Eric Allender, and David A. Mix Barrington. Uniform constant-depth threshold circuits for division and iterated multiplication. J. Comput. Syst. Sci., 65(4):695-716, 2002. Google Scholar
  18. Russell Impagliazzo, Valentine Kabanets, and Avi Wigderson. In search of an easy witness: exponential time vs. probabilistic polynomial time. Journal of Computer and System Sciences, 65(4):672-694, 2002. Google Scholar
  19. Yuval Ishai and Eyal Kushilevitz. Perfect constant-round secure computation via perfect randomizing polynomials. In Proc. 29th International Colloquium on Automata, Languages and Programming (ICALP), pages 244-256, 2002. URL: https://doi.org/10.1007/3-540-45465-9_22.
  20. Hamid Jahanjou, Eric Miles, and Emanuele Viola. Local reductions. In Proc. 42nd International Colloquium on Automata, Languages and Programming (ICALP), pages 749-760, 2015. Google Scholar
  21. Carsten Lund, Lance Fortnow, Howard Karloff, and Noam Nisan. Algebraic methods for interactive proof systems. Journal of the Association for Computing Machinery, 39(4):859-868, 1992. Google Scholar
  22. Cody Murray and R. Ryan Williams. Circuit lower bounds for nondeterministic quasi-polytime: An easy witness lemma for NP and NQP. In Proc. 50th Annual ACM Symposium on Theory of Computing (STOC), pages 890-901, 2018. Google Scholar
  23. Cody D. Murray and R. Ryan Williams. Circuit lower bounds for nondeterministic quasi-polytime from a new easy witness lemma. SIAM Journal of Computing, 49(5), 2020. Google Scholar
  24. Noam Nisan and Avi Wigderson. Hardness vs. randomness. Journal of Computer and System Sciences, 49(2):149-167, 1994. Google Scholar
  25. Alexander A. Razborov. Lower bounds on the size of constant-depth networks over a complete basis with logical addition. Mathematical Notes of the Academy of Science of the USSR, 41(4):333-338, 1987. Google Scholar
  26. Rahul Santhanam. Circuit lower bounds for Merlin-Arthur classes. SIAM Journal of Computing, 39(3):1038-1061, 2009. Google Scholar
  27. Joel I. Seiferas, Michael J. Fischer, and Albert R. Meyer. Separating nondeterministic time complexity classes. J. ACM, 25(1):146-167, 1978. URL: https://doi.org/10.1145/322047.322061.
  28. Ronen Shaltiel and Emanuele Viola. Hardness amplification proofs require majority. SIAM Journal of Computing, 39(7):3122-3154, 2010. Google Scholar
  29. Adi Shamir. IP = PSPACE. Journal of the ACM, 39(4):869-877, 1992. Google Scholar
  30. Roman Smolensky. Algebraic methods in the theory of lower bounds for boolean circuit complexity. In Proc. 19th Annual ACM Symposium on Theory of Computing (STOC), pages 77-82, 1987. Google Scholar
  31. Luca Trevisan and Salil P. Vadhan. Pseudorandomness and average-case complexity via uniform reductions. Computational Complexity, 16(4):331-364, 2007. Google Scholar
  32. Nikhil Vyas. Unpublished manuscript, 2019. Google Scholar
  33. R. Ryan Williams. Natural proofs versus derandomization. SIAM Journal of Computing, 45(2):497-529, 2016. Google Scholar
  34. Richard Ryan Williams. New algorithms and lower bounds for circuits with linear threshold gates. Theory of Computing, 14:Paper No. 17, 25, 2018. Google Scholar
  35. Ryan Williams. Improving exhaustive search implies superpolynomial lower bounds. In Proc. 42nd Annual ACM Symposium on Theory of Computing (STOC), pages 231-240, 2010. Google Scholar
  36. Ryan Williams. Non-uniform ACC circuit lower bounds. In çc26th, pages 115-125, 2011. Google Scholar
  37. Ryan Williams. Improving exhaustive search implies superpolynomial lower bounds. SIAM Journal of Computing, 42(3):1218-1244, 2013. Google Scholar
  38. Ryan Williams. Natural proofs versus derandomization. In Proc. 45th Annual ACM Symposium on Theory of Computing (STOC), pages 21-30, 2013. Google Scholar
  39. Ryan Williams. Nonuniform ACC circuit lower bounds. Journal of the ACM, 61(1):2:1-2:32, 2014. Google Scholar
  40. Andrew C-C. Yao. Separating the polynomial-time hierarchy by oracles. In Proc. 26th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 1-10, 1985. Google Scholar
  41. Stanislav Žák. A Turing machine time hierarchy. Theoretical Computer Science, 26(3):327-333, 1983. Google Scholar
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 About DROPS Imprint Privacy Contact