Skip to content Skip to navigation
2/27/2017 03:30 pm
CoRE A (301)

Hardness of Approximation and PCPs.

Amey Bhangale, Dept. of Computer Science

Defense Committee: Prof. Swastik Kopparty (chair), Prof. Shubhangi Saraf, Prof. Mario Szegedy, Prof. Prasad Raghavendra (University of California, Berkeley)


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.