Natural Proofs Versus Derandomization

Ryan Williams

We study connections between Natural Proofs, derandomization, and the problem of proving "weak" circuit lower bounds such as $\mathsf{NEXP}\not\subset \mathsf{T}{\mathsf{C}}^0$. Natural Proofs hav…