CS Events

PhD Defense

PCPs, CSPs and Property Testing

 

Download as iCal file

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

Bio

NULL

Location : CoRE A (301)

Committee

Prof. Swastik Kopparty (Chair), Prof. Shubhangi Saraf, Prof. Mario Szegedy, Prof. Prasad Raghavendra (University of California) Berkeley)

Event Type: PhD Defense

Organization

Dept. of Computer Science