CS Events

The famous PCP (probabilistically checkable proof) theorem states that one can verify a proof by reading the proof at a very few locations such that if the proof is correct, then the verifier always accepts the proof whereas the verifier rejects the incorrect proof with high probability. The PCP theorem has applications in proving hardness of approximation results for many optimization problems. This thesis is centered around understanding the implications of this theorem as well as studying the components in the proof of the PCP theorem.

Some of the results include efficient procedures for testing a dictator function and low degree functions, a simpler proof of parallel repetition theorem for certain games, the complexity of approximating simultaneous CSPs and covering CSPs and the hardness of approximating Max-Bi-Clique and related problems.