Probabilistic Proofs and NP-Completeness

(a course given by Jiri Sgall, spring 2002)

In this course we will cover the proof of the PCP theorem and its implications for the hardness of approximation.

Here are some pointers to texts used during the course, or providing an alternative coverage of the results.

Sanjeev Arora. Probabilistic Checking of Proofs and Hardness of Approximation Problems, Technical Report CS-TR-476-94, Princeton University, 1995.

Available at: ftp://www.cs.princeton.edu/reports/1994/476.ps.gz or http://www.cs.princeton.edu/~arora/pubs/thesis.ps
A technical report based on the author's Ph.D thesis. Contains the complete proof of the PCP theorem, basic relations to approximation.

Sanjeev Arora, Muli Safra: Probabilistic Checking of Proofs: A New Characterization of NP. Journal of ACM, 45(1):70--122, 1998. An extended abstract appeared in FOCS 1992.

Available at: http://www.cs.princeton.edu/~arora/pubs/as.ps
A journal version of the original paper containing the weaker version of the PCP theorem.

Sanjeev Arora and Carsten Lund and Rajeev Motwani and Madhu Sudan and Mario Szegedy. Proof verification and the hardness of approximation problems. Journal of ACM, 45(3):501-555, 1998. An extended abstract appeared in FOCS 1992.

Available at: http://www.cs.princeton.edu/~arora/pubs/almss.ps

Electronic Colloquium on Computational Complexity

A journal version of the original paper containing the PCP theorem.

Ran Raz, Shmuel Safra: Sub-Constant Error-Probability Low-Degree Test, and a Sub-Constant Error-Probability PCP Characterization of NP. Manuscript, 1996. An extended abstract appeared in STOC '97.

Available at: http://www.wisdom.weizmann.ac.il/~ranraz/publications/Prsconf.ps (STOC version)
Full version available in a local copy: Part I and Part II

Contains the improved and simplified low-degree test. The actual test is contained in Part II. The STOC version contains the 3-dimensional version (read it first!).

Sanjeev Arora, Madhu Sudan. Improved low-degree testing and its applications. An extended abstract appeared in STOC 1997.

Available at: http://www.cs.princeton.edu/~arora/pubs/ldtest.ps
or Electronic Colloquium on Computational Complexity , Report TR97-003
An improved analysis of the original low-degree test. The results are similar as in the previous item, but achieved using the means of algebraic geometry.

Mihir Bellare, Oded Goldreich, Madhu Sudan. Free bits, PCP and Non-Approximability - Towards tight results. SIAM J. Comput. 27(3): 804-915, 1998. An extended abstract appeared in FOCS 1995.

Available at: Electronic Colloquium on Computational Complexity, Report TR95-024
Introduced the notion of free bits. An excellent survey of the current best inapproximability results (including those based on the successive work, up to summer 1997). Many results from here are now improved (building on this work).

Ran Raz. A Parallel repetition theorem. SIAM J. Comput. 27(3):763-803, 1998. An extended abstract appeared in STOC 1995.

Available at: http://www.wisdom.weizmann.ac.il/~ranraz/publications/Pparal1.ps

Proof of the parallel repetition theorem.

Johan Håstad. Some optimal inapproximability results. Journal of ACM 48:798--859, 2001. An extended abstract appeared in STOC 1996.

Available at: http://www.nada.kth.se/~johanh/optimalinap.ps
or Electronic Colloquium on Computational Complexity , Report TR97-037
Optimal inapproximability results for linear equations and satisfiability. An extended abstract appeared in FOCS 1996.

Johan Håstad. Clique is hard to approximate within $n^{1-\epsilon}$. Acta Mathematica 182:105-142, 1999.

Available at: http://www.nada.kth.se/~johanh/cliqueinap.ps
or Electronic Colloquium on Computational Complexity, Report TR97-038

Madhu Sudan and Luca Trevisan. Probabilistically Checkable Proofs with Low Amortized Query Complexity. An extended abstract appeared in FOCS 1998.

Available at: http://www.cs.berkeley.edu/~luca/pubs/st98.ps.Z
or Electronic Colloquium on Computational Complexity , Report TR98-040

Alex Samorodnitsky and Luca Trevisan. A PCP Characterization of NP with Optimal Amortized Query Complexity. An extended abstract appeared in STOC 2000.

Available at: http://www.cs.berkeley.edu/~luca/pubs/st-full.ps
A simplified version of Hastad inapproximability result for max clique. Depends heavily on the previous paper.

Some books covering parts of the proof of the PCP theorem or its relation to hardness of approximation are listed below.

G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, M. Protasi: Complexity and Approximation. Springer, 1999.
E. W. Mayr, H. J. Proemel, A. Steger (eds.): Lectures on Proof Verification and Approximation Algorithms. LNCS 1367. Springer, 1998.
D. S. Hochbaum: Approximation Algorithms for NP-hard problems. PWS Publishing Company, 1997.
R. Motwani, P. Raghavan: Randomized algorithms. Cambridge Univ. Press, 1995.

Last changed June 4, 2002