Concepedia

Pcp Class

PCP Class is a complexity-theoretic class of decision problems solvable by a probabilistically checkable proof system where the verifier uses a bounded amount of randomness and queries only a constant number of bits of the proof.

71

Publications

3.9K

Citations

178

Authors

89

Institutions

Publications per year

2017–2026

8

Variants

Probabilistically Checkable Proofs Class

Parents

Publications

71

Proof verification and hardness of approximation problems

Sanjeev Arora, Carsten Lund, R. Motwani et al. · 1992 · 744 citations

, , +16

The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative Type Metrics into \ell 1

Subhash Khot, Nisheeth K. Vishnoi · 2005 · 275 citations

, , +11

Toward a Unified Theory of the CSP–CFP Link

Isaiah Yeshayahu Marom · Journal of Business Ethics · 2006 · 240 citations

, , +5

Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding

Eli Ben‐Sasson, Oded Goldreich, Prahladh Harsha et al. · SIAM Journal on Computing · 2006 · 240 citations · Full text

, , +15

MIP* = RE

Zhengfeng Ji, Anand Natarajan, Thomas Vidick et al. · Communications of the ACM · 2021 · 167 citations · Full text

, , +14

1–5 of 71

Authors

178

  1. MS
    Madhu Sudan

    Massachusetts Institute of Technology, United States

    9 publications · 1.5K citations

    9

    h-index

  2. PH
    Prahladh Harsha

    Tata Institute of Fundamental Research, India

    8 publications · 551 citations

    8

    h-index

  3. SV
    Salil Vadhan

    Harvard University Press, United States

    6 publications · 464 citations

    6

    h-index

  4. OG
    Oded Goldreich

    Weizmann Institute of Science, Israel

    6 publications · 627 citations

    6

    h-index

  5. JH
    Johan Håstad

    KTH Royal Institute of Technology, Sweden

    5 publications · 145 citations

    5

    h-index

1–5 of 178

Institutions

89

  1. Weizmann Institute of Science

    Rehovot, Israel

    11 h-index

    19 publications

    1.2K citations

  2. Massachusetts Institute of Technology

    Cambridge, United States

    10 h-index

    19 publications

    1.5K citations

  3. Technion – Israel Institute of Technology

    Haifa, Israel

    6 h-index

    8 publications

    330 citations

  4. Harvard University

    Cambridge, United States

    5 h-index

    5 publications

    452 citations

  5. KTH Royal Institute of Technology

    Stockholm, Sweden

    5 h-index

    5 publications

    145 citations

  6. Institute for Advanced Study

    Princeton, United States

    5 h-index

    7 publications

    306 citations

  7. Georgia Institute of Technology

    Atlanta, United States

    4 h-index

    6 publications

    407 citations

  8. Princeton University

    Princeton, United States

    4 h-index

    4 publications

    68 citations

1–8 of 89

Venues

  1. Computational Complexity

    CC · 4 publications · 93 citations

    4

    h-index

  2. SIAM Journal on Computing

    3 publications · 313 citations

    3

    h-index

  3. ArXiv.org

    Repository · 2 publications · 30 citations

    2

    h-index

  4. 2

    h-index

  5. Organometallics

    2 publications · 128 citations

    2

    h-index

1–5