Property Testing, PCPs and CSP

Many optimization problems can be modeled as constraint satisfaction problems (CSPs). Hence understanding the complexity of solving or approximating CSPs is a fundamental problem in computer science. The famous PCP (probabilistically checkable proof) Theorem states that certain CSPs are hard to approximate within a constant factor. In the language of proof verification, the theorem implies that a proof of a mathematical statement can be written in a specific format such that it allows an sublinear time verification of the proof. Thus, property testing procedures are central to PCPs, and in fact the proof of the PCP theorem involves many interesting property testing algorithms.;Some of the highlights of this dissertation include the following results:;1. Low degree testing is one of the important components in the proof of the PCP theorem and Dictatorship testing is central in proving hardness of approximation results. This thesis presents a Cube vs Cube low degree test which has significantly better parameters than the previously known tests. We also improve on the soundness of k -bit dictatorship test with perfect completeness.;2. In the area of inapproximability, this thesis offers a complete characterization of approximating the covering number of a CSP, assuming a covering variant of UNIQUE GAMES CONJECTURE . We also prove tight inapproximability results for Bi-Covering problem.;3. This thesis studies CSPs from a multi-objective point of view. We give almost optimal approximation algorithms for multi-objective M AX-CSP (simultaneous CSPs), and also prove inapproximability results.