ECCC-Report TR19-031https://eccc.weizmann.ac.il/report/2019/031Comments and Revisions published for TR19-031en-usSat, 13 Jul 2019 01:03:19 +0300
Revision 1
| Non-deterministic Quasi-Polynomial Time is Average-case Hard for ACC Circuits |
Lijie Chen
https://eccc.weizmann.ac.il/report/2019/031#revision1Following 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 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/log^c(n)-approximable by polynomial-size ACC^0 circuits. In fact, our lower bound holds for a larger circuit class: 2^(log^a n)-size ACC^0 circuits with a layer of threshold gates at the bottom, 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 NC^1-complete language which is random self-reducible.
The sub-exponential witness-size lower bound for NE against ACC^0 and 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 ACC^0 of THR exploited by us is the existence of a non-trivial SAT algorithm for ACC^0 of THR [Williams, STOC 2014]. Therefore, for any typical circuit class C, our results apply to them as well if the corresponding non-trivial SAT (in fact, GAP-UNSAT) algorithms are discovered.Sat, 13 Jul 2019 01:03:19 +0300https://eccc.weizmann.ac.il/report/2019/031#revision1
Paper TR19-031
| Non-deterministic Quasi-Polynomial Time is Average-case Hard for ACC Circuits |
Lijie Chen
https://eccc.weizmann.ac.il/report/2019/031Following 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 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/log^c(n)-approximable by polynomial-size ACC^0 circuits. In fact, our lower bound holds for a larger circuit class: 2^(log^a n)-size ACC^0 circuits with a layer of threshold gates at the bottom, 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 NC^1-complete language which is random self-reducible.
The sub-exponential witness-size lower bound for NE against ACC^0 and 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 ACC^0 of THR exploited by us is the existence of a non-trivial SAT algorithm for ACC^0 of THR [Williams, STOC 2014]. Therefore, for any typical circuit class C, our results apply to them as well if the corresponding non-trivial SAT (in fact, GAP-UNSAT) algorithms are discovered.Tue, 05 Mar 2019 01:07:29 +0200https://eccc.weizmann.ac.il/report/2019/031