Back to PCP
Back to notes

# Historical Development of PCP

40%

## History of results

The way we present the historical development of PCP theorems is based on the survey of Sudan (Sudan, 2009).

### Phase 0: Folklore

• $\NP=\PCP[0,\poly(n)]$
• $\NP=\PCP[O(\log n),\poly(n)]$

## References

1. Sudan, M. (2009). Probabilistically checkable proofs. Communications of the ACM, 52(3), 76–84.
2. Babai, L., Fortnow, L., & Lund, C. (1990). Nondeterministic exponential time has two-prover interactive protocols. In Foundations of Computer Science, 1990. Proceedings., 31st Annual Symposium on (pp. 16–25). IEEE.
3. Babai, L., Fortnow, L., Levin, L. A., & Szegedy, M. (1991). Checking computations in polylogarithmic time. In Proceedings of the twenty-third annual ACM symposium on Theory of computing (pp. 21–32). ACM.
4. Arora, S., & Safra, S. (1998). Probabilistic checking of proofs: A new characterization of NP. Journal of the ACM (JACM), 45(1), 70–122.
5. Arora, S., Lund, C., Motwani, R., Sudan, M., & Szegedy, M. (1998). Proof verification and the hardness of approximation problems. Journal of the ACM (JACM), 45(3), 501–555.
6. Håstad, J. (2001). Some optimal inapproximability results. Journal of the ACM (JACM), 48(4), 798–859.
7. Guruswami, V., Lewin, D., Sudan, M., & Trevisan, L. (1998). A tight characterization of NP with 3 query PCPs. In Foundations of Computer Science, 1998. Proceedings. 39th Annual Symposium on (pp. 8–17). IEEE.
8. Polishchuk, A., & Spielman, D. A. (1994). Nearly-linear size holographic proofs. In Proceedings of the twenty-sixth annual ACM symposium on Theory of computing (pp. 194–203). ACM.
9. Karloff, H., & Zwick, U. (1997). A 7/8-approximation algorithm for MAX 3SAT? In Foundations of Computer Science, 1997. Proceedings., 38th Annual Symposium on (pp. 406–415). IEEE.