Almost-natural proofs

DOI10.1016/j.jcss.2010.06.017zbMath1215.68100OpenAlexW2110905926MaRDI QIDQ716305

Timothy Y. Chow

Publication date: 28 April 2011

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2010.06.017

zbMATH Keywords

circuit lower boundnatural proof

Mathematics Subject Classification ID

Related Items (5)

Binary pattern tile set synthesis is NP-hard ⋮ Feasibly constructive proofs of succinct weak circuit lower bounds ⋮ Natural Proofs versus Derandomization ⋮ Unnamed Item ⋮ On the complexity of nonuniform wavelength-based machine

Cites Work

• Unnamed Item
• Unnamed Item
• A Boolean function requiring 3n network size
• Circuit minimization problem
• Cracks in the Defenses: Scouting Out Approaches on Circuit Lower Bounds
• The number of Boolean functions computed by formulas of a given size
• Explicit lower bound of 4.5n - o(n) for boolena circuits
• Natural proofs

This page was built for publication: Almost-natural proofs