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

Authors

55

  1. PM
    P. Madhusudan

    University of Illinois Urbana-Champaign, United States

    6 publications · 237 citations

    6

    h-index

  2. SA
    Scott Aaronson

    Massachusetts Institute of Technology, United States

    4 publications · 296 citations

    4

    h-index

  3. XQ
    Xiaokang Qiu

    University of Illinois Urbana-Champaign, United States

    4 publications · 182 citations

    4

    h-index

  4. PG
    Pranav Garg

    University of Illinois Urbana-Champaign, United States

    3 publications · 134 citations

    3

    h-index

  5. AW
    Avi Wigderson

    Hebrew University of Jerusalem, Israel

    3 publications · 237 citations

    3

    h-index

1–5 of 55

Venues

  1. Journal of Symbolic Logic

    3 publications · 75 citations

    3

    h-index

  2. Journal of the ACM

    JACM · 2 publications · 35 citations

    2

    h-index

  3. ACM SIGPLAN Notices

    2 publications · 41 citations

    2

    h-index

  4. ACM Transactions on Computation Theory

    TOCT · 2 publications · 166 citations

    2

    h-index

  5. American Journal of Mathematics

    1 publications · 250 citations

    1

    h-index

1–5