Strong average-case lower bounds from non-trivial derandomization Article Swipe

PDF

Related Concepts

Pseudorandom number generator Electronic circuit Pseudorandom generator Generator (circuit theory) Mathematics Combinatorics Constant (computer programming) Binary logarithm Circuit complexity Discrete mathematics Computer science Algorithm Physics Programming language Power (physics) Quantum mechanics

Lijie Chen , Hanlin Ren ·

YOU? · · 2020 · Open Access · · DOI: https://doi.org/10.1145/3357713.3384279 · OA: W3035226643

We prove that for all constants a, NQP = NTIME[n polylog(n)] cannot be (1/2 + 2−log a n )-approximated by 2log a n -size ACC 0 ∘ 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/√n)-approximated by AC 0[⊕] circuits. As a straightforward application, we obtain an infinitely often ( NE ∩ coNE)/1-computable pseudorandom generator for poly-size ACC 0 circuits with seed length 2logє n , for all є > 0.