Concepedia

Probabilistically Checkable Proofs

Probabilistically Checkable Proofs is a computational proof system in which a probabilistic verifier can check the validity of a proof by examining only a constant number of bits from it, with high confidence, distinguishing correct proofs from incorrect ones with high probability based on limited, randomized queries.

74

Publications

7K

Citations

97

Authors

59

Institutions

Publications per year

2017–2026

6

Parents

Publications

74

Probabilistic checking of proofs

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

, , +14

Free Bits, PCPs, and Nonapproximability---Towards Tight Results

Mihir Bellare, Oded Goldreich, Madhu Sudan · SIAM Journal on Computing · 1998 · 455 citations

, , +16

Zero Knowledge and the Chromatic Number

Uriel Feige, Joe Kilian · Journal of Computer and System Sciences · 1998 · 335 citations

, , +15

Efficient probabilistically checkable proofs and applications to approximations

Mihir Bellare, S. Goldwasser, Carsten Lund et al. · 1993 · 318 citations

, , +8

Noise stability of functions with low influences: Invariance and optimality

Elchanan Mossel, Ryan O’Donnell, Krzysztof Oleszkiewicz · Annals of Mathematics · 2010 · 295 citations · Full text

, , +11

1–5 of 74

Authors

97

  1. EB
    Eli Ben‐Sasson

    Technion – Israel Institute of Technology, Israel

    14 publications · 901 citations

    13

    h-index

  2. MS
    Madhu Sudan

    Massachusetts Institute of Technology, United States

    14 publications · 1.5K citations

    13

    h-index

  3. CL
    Carsten Lund

    AT&T (United States), United States

    6 publications · 470 citations

    6

    h-index

  4. ID
    Irit Dinur

    Weizmann Institute of Science, Israel

    6 publications · 398 citations

    6

    h-index

  5. AW
    Avi Wigderson

    Hebrew University of Jerusalem, Israel

    6 publications · 290 citations

    6

    h-index

1–5 of 97

Institutions

59

  1. Massachusetts Institute of Technology

    Cambridge, United States

    13 h-index

    18 publications

    1.8K citations

  2. University of California, Berkeley

    Berkeley, United States

    12 h-index

    12 publications

    1.3K citations

  3. Technion – Israel Institute of Technology

    Haifa, Israel

    11 h-index

    21 publications

    543 citations

  4. Institute for Advanced Study

    Princeton, United States

    8 h-index

    10 publications

    423 citations

  5. Weizmann Institute of Science

    Rehovot, Israel

    8 h-index

    8 publications

    973 citations

  6. Princeton University

    Princeton, United States

    8 h-index

    10 publications

    1.6K citations

  7. Harvard University

    Cambridge, United States

    5 h-index

    6 publications

    708 citations

  8. AT&T (United States)

    Bedminster, United States

    5 h-index

    9 publications

    451 citations

1–8 of 59

Venues

  1. SIAM Journal on Computing

    13 publications · 1.6K citations

    13

    h-index

  2. Journal of the ACM

    JACM · 3 publications · 1.4K citations

    3

    h-index

  3. IACR Cryptology ePrint Archive

    Repository · 3 publications · 71 citations

    3

    h-index

  4. DROPS (Schloss Dagstuhl – Leibniz Center for Informatics)

    Repository · 3 publications · 182 citations

    3

    h-index

  5. ArXiv.org

    Repository · 2 publications · 51 citations

    2

    h-index

1–5