We prove that, unconditionally, for all constants a, NQP =
NTIME[n^polylog(n)] cannot be (1/2 + 2^(-log^a n) )-approximated by
2^(log^a n)-size ACC^0 circuits. Previously, it was even open
whether E^NP can be (1/2+1/sqrt(n))-approximated by AC^0[2...
Read More