Natural proofs versus derandomization

DOI10.1145/2488608.2488612MaRDI QIDQ6828773zbMATH OpenFDO

Authors Ryan Williams

Publication date 7 August 2014

Published in Proceedings of the forty-fifth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

zbMATH Keywords

lower boundscircuit complexityACCnatural proofs

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20)

This page was built for publication: Natural proofs versus derandomization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6828773)