In 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.