From Proof Complexity to Circuit Complexity via Interactive Protocols

Noel Arteche, Erfan Khaniki, Ján Pich +1

Folklore in complexity theory suspects that circuit lower bounds against ${\mathbf{NC}}^1$ or $\mathbf{P}/\mathrm{poly}$, currently out of reach, are a necessary step towards p…