Concepedia

Proof Complexity

Proof Complexity is a branch of theoretical computer science that studies the computational resources required by proof systems to establish the validity of propositional tautologies, particularly focusing on the minimal size or length of proofs relative to the complexity of the statements being proved.

1.6K

Publications

100.7K

Citations

2.2K

Authors

792

Institutions

Publications per year

2017–2026

177

Parents

Children

Publications

1.6K

The complexity of theorem-proving procedures

Stephen Cook · 1971 · 6.2K citations · Full text

, , +17

On a Problem of Formal Logic

Frank Plumpton Ramsey · Proceedings of the London Mathematical Society · 1930 · 1.9K citations

, , +11

Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems

Oded Goldreich, Silvio Micali, Avi Wigderson · Journal of the ACM · 1991 · 1.4K citations

, , +8

The knowledge complexity of interactive proof-systems

Sbafi Goldwasser, Silvio Micali, Charles Rackoff · 1985 · 1.2K citations · Full text

, , +8

Probabilistic checking of proofs

Sanjeev Arora · Journal of the ACM · 1998 · 1.2K citations · Full text

, , +14

1–5 of 1.6K

Authors

2.2K

  1. TP
    Toniann Pitassi

    University of Toronto, Canada

    25 publications · 1.4K citations

    20

    h-index

  2. EB
    Eli Ben‐Sasson

    Technion – Israel Institute of Technology, Israel

    27 publications · 1.8K citations

    18

    h-index

  3. OG
    Oded Goldreich

    Weizmann Institute of Science, Israel

    16 publications · 3.6K citations

    16

    h-index

  4. SR
    Samuel R. Buss

    University of California San Diego, United States

    16 publications · 724 citations

    14

    h-index

  5. JN
    Jakob Nordstr”öm

    KTH Royal Institute of Technology, Sweden

    19 publications · 515 citations

    14

    h-index

1–5 of 2.2K

Institutions

792

  1. Weizmann Institute of Science

    Rehovot, Israel

    31 h-index

    60 publications

    9.3K citations

  2. Massachusetts Institute of Technology

    Cambridge, United States

    28 h-index

    67 publications

    6.8K citations

  3. Centre National de la Recherche Scientifique

    Paris, France

    27 h-index

    80 publications

    3.4K citations

  4. University of Toronto

    Toronto, Canada

    27 h-index

    61 publications

    11K citations

  5. University of California San Diego

    San Diego, United States

    26 h-index

    43 publications

    3.1K citations

  6. Microsoft (United States)

    Redmond, United States

    25 h-index

    30 publications

    2.2K citations

  7. Technion – Israel Institute of Technology

    Haifa, Israel

    21 h-index

    48 publications

    3.2K citations

  8. Princeton University

    Princeton, United States

    21 h-index

    36 publications

    3.4K citations

1–8 of 792

Venues

  1. Theoretical Computer Science

    78 publications · 3.9K citations

    32

    h-index

  2. Journal of Automated Reasoning

    54 publications · 2.6K citations

    26

    h-index

  3. Journal of Symbolic Logic

    31 publications · 4K citations

    25

    h-index

  4. Annals of Pure and Applied Logic

    44 publications · 1.7K citations

    25

    h-index

  5. SIAM Journal on Computing

    24 publications · 3.9K citations

    24

    h-index

1–5