A tutorial 0on PCP theorem

Date Thursday, October 20, 5:20-7:30 pm
the first tutorial of

5-hour tutorial
"PCP theorem, Interactive Proofs and Inapproximability of
Optimization Problems"


This talk would be more a tutorial, then a seminar. Full proofs, explanations and background materials will be given. I have given it once already in UoQ and this tutorial is quite ready in sense of quality of presentation.

PCP theorem is considered to be one of the major development in TCS in 90s. Perhaps, since 1992 every STOC and FOCS conference has at least one article strongly related to the PCP theorem.

Basically the PCP theorem provides a new characterization of NP class as a class of languages, a membership problem of which can be solved by the logarithmic number of random bits and the constant number of proof bits. (sounds miracle? The constant number of bits is actually needed instead of polynomial to proof a membership of the word.)
The original proof based on algebraic technique is quite complicated (around 20 pages of proof). The new proof based on combinatorial techniques (zig-zag products) was discovered this year by Irit Dinur.
Using other version of interactive proof systems we can capture PSPACE and NEXPTIME class and investigate some interesting properties of them.

NPO means NP optimization problem. NPO is a search version of NP class which is defined to be a class of decission problems. The NPO problem required to find a minimal (or maximal) solution among given one. For example, a Traveling Salesman Problem expressed as a search problem (Find a minimal lengh route in the graph which visit all vertices ones) would be an example of NPO problem. Usually NPO problem, a search version of NP decission problems belongs to FP^NP or FP^NP(log n) - hard classes indeed.
Since assuming P is not equal NP, there does not exist a polynomial algorithm to solve EXACTLY NP-hard-problems, given a NP-hard NPO problem it would be natural to ask, if a polynomial-time algorithm exists which can solve a problem with some approximation quality.
It was discovered that there exists a few approximation classes of NPO problems, which put certain bounds on approximation quality of algorithms for those problems. PCP theorem is useful to prove in-approximation properties of NPO problems.

Besides PCP theorem other important for theoretical computer science techniques will be introduced. Expanders are graphs which posses good expansion properties. (n,d,c) expander is a d-regular undirected graph with n vertices, such that if a set of vertices S chooses such that |S| < |n|/2, then a cardinality of a set of vertices adjacent to S is not less then c|S| Expanders are useful in computational complexity, error-correcting codes, communication networks.
Using expanders and PCP theorem we will prove n^\epsilon-inapproximability of MAX CLIQUE problem and NP-hardness of MAX 3SAT5 (SAT with 3 variables per clause and each variable is used not more then 5 times)