Derandomized Parallel Repetition via Structured PCPs

A PCP is a proof system for NP in which the proof can be checked by a probabilistic verifier. The verifier is only allowed to read a very small portion of the proof and in return is allowed to err with some bounded probability. The probability that the verifier accepts a proof of a false claim is called the soundness error and is an important parameter of a PCP system that one seeks to minimize. Constructing PCPs with subconstant soundness error and, at the same time, a minimal number of queries into the proof (namely two) is especially important due to applications for inapproximability.