Nondeterministic Quasi-Polynomial Time is Average-Case Hard for \(\textsf{ACC}\) Circuits
Lijie Chen · SIAM Journal on Computing · 2024
Abstract. Following the seminal work of [R. R. Williams, J. ACM, 61 (2014)], in a recent breakthrough, [C. D. Murray and R. R. Williams, STOC 2018] proved that [Formula: see text] (nondeterministic quasi-polynomial time) does not have polynomial-size [Formula: see text] circuits (constant depth circuits consisting of [Formula: see text]/[Formula: see text]/[Formula: see text] gates for a fixed constant [Formula: see text], a frontier class in circuit complexity). We strengthen the above lower bound to an average-case one, by proving that for all constants [Formula: see text], there is a language in [Formula: see text] that cannot be [Formula: see text]-approximated by polynomial-size [Formula: see text] circuits. Our work also improves the average-case lower bound for [Formula: see text] against polynomial-size [Formula: see text] circuits by [R. Chen, I. C. Oliveira, and R. Santhanam, LATIN 2018, pp. 317–330]. Our new lower bound builds on several interesting components, including the following: 1. Barrington’s theorem and the existence of an [Formula: see text]-complete language that is random self-reducible. 2. The subexponential witness-size lower bound for [Formula: see text] against [Formula: see text] and the conditional nondeterministic pseudorandom generator (PRG) construction in [R. R. Williams, SIAM J. Comput., 45 (2016), pp. 497–529]. 3. An “almost” almost-everywhere [Formula: see text] average-case lower bound (which strengthens the corresponding worst-case lower bound in [C. D. Murray and R. R. Williams, STOC 2018]). 4. A [Formula: see text]-complete language that is downward self-reducible, same-length checkable, error-correctable, and paddable. Moreover, all its reducibility properties have corresponding low-depth nonadaptive oracle circuits. Our construction builds on [L. Trevisan and S. P. Vadhan, Comput. Complexity, 16 (2007), pp. 331–364]. Like other lower bounds proved via the “algorithmic approach,” the only property of [Formula: see text] exploited by us is the existence of a nontrivial [Formula: see text] algorithm for [Formula: see text] [R. R. Williams, J. ACM, 61 (2014)]. Therefore, for any typical circuit class [Formula: see text], our results apply to [Formula: see text] as well if a nontrivial [Formula: see text] (in fact, [Formula: see text]) algorithm for [Formula: see text] is discovered.