All reports by Author Hanlin Ren:

__
TR20-010
| 12th February 2020
__

Lijie Chen, Hanlin Ren#### Strong Average-Case Circuit Lower Bounds from Non-trivial Derandomization

Lijie Chen, Hanlin Ren

We prove that 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 of THR circuits (ACC^0 circuits with a bottom layer of THR gates). Previously, it was even open whether E^NP can be (1/2+1/sqrt{n})-approximated by AC^0[2] circuits. As a straightforward application, ... more >>>