ECCC-Report TR17-173https://eccc.weizmann.ac.il/report/2017/173Comments and Revisions published for TR17-173en-usMon, 06 Nov 2017 19:03:44 +0200
Paper TR17-173
| An Average-Case Lower Bound against ACC^0 |
Rahul Santhanam,
Igor Carboni Oliveira,
Ruiwen Chen
https://eccc.weizmann.ac.il/report/2017/173In a seminal work, Williams [Wil14] showed that NEXP (non-deterministic exponential time) does not have polynomial-size ACC^0 circuits. Williams' technique inherently gives a worst-case lower bound, and until now, no average-case version of his result was known.
We show that there is a language L in NEXP (resp. EXP^NP) and a function epsilon(n) = 1/\log(n)^{\omega(1)} (resp. 1/n^{\Omega(1)}) such that no sequence of polynomial size ACC^0 circuits solves L on more than a 1/2+epsilon(n) fraction of inputs of length n for all large enough n.
Complementing this result, we give a nontrivial pseudo-random generator against polynomial-size ACC^0[6] circuits. We also show that learning algorithms for quasi-polynomial size ACC^0 circuits running in time 2^n/n^\omega(1) imply lower bounds for the randomised exponential time classes RE (randomized time 2^{O(n)} with one-sided error) and ZPE/1 (zero-error randomized time 2^{O(n)} with 1 bit of advice) against polynomial size ACC^0 circuits. This strengthens results of a subset of the authors.Mon, 06 Nov 2017 19:03:44 +0200https://eccc.weizmann.ac.il/report/2017/173