CS Events


Hardness of Approximation and PCPs.


Download as iCal file

Monday, February 27, 2017, 03: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 accept the proof where as 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 proving hardness results as well as studying the components in the proof of the PCP theorem.

A low degree test is one of the important components in proving the PCP theorem. In this talk, I will talk about a recent result about a low degree test. Our main result is a new combinatorial proof for a low degree test that comes closer to the soundness limit, as it works for all epsilon ≥ poly(d)/|F|^{1/2} , where d is the degree. This should be compared to the previously best soundness value of epsilon ≥ poly(m, d)/ |F|^{1/8}. Our soundness limit improves upon the dependence on the field size and does not depend on the dimension of the ambient space. Our proof is combinatorial and direct: unlike the previous proofs, it proceeds in one shot and does not require induction on the dimension of the ambient space.

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: Pre-Defense



Dept. of Computer Science