Natural proofs

DOI10.1145/195058.195134MaRDI QIDQ5890841zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Steven Rudich, Alexander Razborov

Publication date 1 September 2016

Published in Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/195058.195134

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)

Recommendations

• Natural proofs
• Almost-natural proofs
• Models of lower-bounds proofs

Cited in

(27)

• Bounded simultaneous messages
• Almost-natural proofs
• Circuit complexity before the dawn of the new millennium
• A note on uniform circuit lower bounds for the counting hierarchy (extended abstract)
• Models of lower-bounds proofs
• What is \dots a natural proof?
• One-tape Turing machine and branching program lower bounds for MCSP
• Exploring crypto dark matter: new simple PRF candidates and their applications
• Circuit lower bounds à la Kolmogorov
• On the limits of gate elimination
• Low-complexity weak pseudorandom functions in \(\mathtt{AC}0[\mathtt{MOD}2]\)
• Lower bounds for unrestricted Boolean circuits: open problems
• Optimal bounds for the approximation of Boolean functions and some applications
• Asymptotic spectra: theory, applications, and extensions
• The correlation between parity and quadratic polynomials mod \(3\)
• One-tape Turing machine and branching program lower bounds for MCSP
• Natural proofs
• Pseudorandom functions: three decades later
• Barriers for rank methods in arithmetic complexity
• The circuit-input game, natural proofs, and testing circuits with data
• Structural lower bounds on black-box constructions of pseudorandom functions
• Quantum depth in the random oracle model
• Small bias requires large formulas
• The hunting of the SNARK
• Pseudorandom strings from pseudorandom quantum states
• Understanding the thermodynamics of computation: a pedagogical overview
• Cracks in the Defenses: Scouting Out Approaches on Circuit Lower Bounds

This page was built for publication: Natural proofs

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