Non-deterministic Quasi-Polynomial Time is Average-Case Hard for ACC Circuits

摘要: 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 ACC^0 circuits. We strengthen above lower bound to an average case one, by proving for all constants c, there is language NQP, which 1/2+1/log^c(n)-approximable In fact, our holds larger circuit class: 2^(log^a n)-size circuits with layer threshold gates at bottom, a. Our also improves average-case NEXP against ACC [Chen, Oliveira, Santhanam, LATIN 2018]. new builds on several interesting components, including: • Barrington's theorem existence NC^1-complete random self-reducible. The sub-exponential witness-size NE conditional non-deterministic PRG construction SICOMP 2016]. An “almost'' almost-everywhere MA (which strengthens corresponding worst-case 2018]). A PSPACE-complete same-length checkable, error-correctable has some other nice reducibility properties, [Trevisan Vadhan, Computational Complexity 2007]. Moreover, its properties low-depth non-adaptive oracle Like bounds via ``algorithmic approach'', only property THR exploited us non-trivial SAT algorithm 2014]. Therefore, any typical class l, results apply them as well if (in GAP-UNSAT) algorithms are discovered.