PCPs, CSPs and Property Testing
Wednesday, March 29, 2017, 01:30pm
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.
Speaker: Amey Bhangale
Location : CoRE A (301)
Prof. Swastik Kopparty (Chair), Prof. Shubhangi Saraf, Prof. Mario Szegedy, Prof. Prasad Raghavendra (University of California) Berkeley)
Event Type: PhD Defense
Dept. of Computer Science