An average-case lower bound against ACC$^0$
In a seminal work, Williams [22] showed that NEXP (nondeterministic exponential time) does not have polynomial-size ACC0 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...
| Main Authors: | , , |
|---|---|
| Format: | Conference item |
| Published: |
Springer, Cham
2018
|