Natural Proofs
Natural Proofs is a theoretical framework in computational complexity theory that identifies a class of proof techniques capable of establishing lower bounds on circuit complexity, distinguished by their constructive and large-category properties which, under plausible cryptographic assumptions, are inherently limited in resolving fundamental separation problems such as P versus NP.
33
Publications
1.8K
Citations
55
Authors
39
Institutions
Publications per year
2017–2026
6
Parents
33
Lower bounds for natural proof systems
Dexter Kozen · 1977 · 446 citations
Almost Automorphic Functions on Groups
William A. Veech · American Journal of Mathematics · 1965 · 250 citations
Scott Aaronson, Avi Wigderson · ACM Transactions on Computation Theory · 2009 · 156 citations
Natural proofs for structure, data, and separation
Xiaokang Qiu, Pranav Garg, Andrei Ștefănescu et al. · 2013 · 81 citations
Alexander Razborov, Steven Rudich · 1994 · 80 citations
1–5 of 33
55
6
h-index
4
h-index
4
h-index
3
h-index
3
h-index
1–5 of 55
39
University of Illinois Urbana-Champaign
Urbana, United States
6 h-index
16 publications
678 citations
Massachusetts Institute of Technology
Cambridge, United States
3 h-index
3 publications
89 citations

National Institute of Informatics
Tokyo, Japan
2 h-index
2 publications
25 citations
University of Cambridge
Cambridge, United Kingdom
2 h-index
3 publications
113 citations
University of California San Diego
San Diego, United States
2 h-index
3 publications
124 citations

University of Warwick
Coventry, United Kingdom
2 h-index
3 publications
35 citations
University of Oxford
Oxford, United Kingdom
2 h-index
5 publications
65 citations
Moscow Institute of Thermal Technology
Moscow, Russia
2 h-index
2 publications
173 citations
1–8 of 39
3 publications · 75 citations
3
h-index
JACM · 2 publications · 35 citations
2
h-index
2 publications · 41 citations
2
h-index
TOCT · 2 publications · 166 citations
2
h-index
1 publications · 250 citations
1
h-index
1–5