Non-deterministic Quasi-Polynomial Time is Average-Case Hard for ACC Circuits
Lijie Chen · 2019
Following the seminal work of [Williams, J. ACM 2014], in a recent breakthrough, [Murray and Williams, STOC 2018] proved that NQP (non-deterministic quasi-polynomial time) does not have polynomial-size ACC0circuits. We strengthen the above lower bound to an average case one, by proving that for all constants c, there is a language in NQP, which is not 1/2+1/logc(n)-approximable by polynomial-size ACC0circuits. In fact, our lower bound holds for a larger circuit class: 2(logan)-size ACC0circuits with a layer of threshold gates at the bottom (ACC ο THR circuits), for all constants a. Our work also improves the average-case lower bound for NEXP against polynomial-size ACC circuits by [Chen, Oliveira, and Santhanam, LATIN 2018]. Our new lower bound builds on several interesting components, including: : Barrington's theorem and the existence of an NC1-complete language which is random self-reducible. : The sub-exponential witness-size lower bound for NE against ACC0and the conditional non-deterministic PRG construction in [Williams, SICOMP 2016]. : An “almost'' almost-everywhere MA average-case lower bound (which strengthens the corresponding worst-case lower bound in [Murray and Williams, STOC 2018]). A PSPACE-complete language which is same-length checkable, error-correctable and also has some other nice reducibility properties, which builds on [Trevisan and Vadhan, Computational Complexity 2007]. Moreover, all its reducibility properties have corresponding low-depth non-adaptive oracle circuits. Like other lower bounds proved via the "algorithmic approach'', the only property of ACC0ο THR exploited by us is the existence of a non-trivial SAT algorithm for ACC0ο THR [Williams, STOC 2014]. Therefore, for any typical circuit class ℓ, our results apply to them as well if the corresponding non-trivial SAT (in fact, GAP-UNSAT) algorithms are discovered.