Optimization problems that are NP-hard, and thus conjectured not to have efficient algorithms, arise in many of the areas of human knowledge. Reconstructing phylogeny, finding market equilibrium, scheduling flights and detecting bottlenecks in networks are all examples of such problems. Algorithmists are often able to design algorithms that approximate the optimum efficiently. However, for many problems the approximation is quite crude. Moreover, finding better approximation often turns out to be NP-hard.

Understanding the approximability of NP-hard problems is intimately related to the deep theory of probabilistically checkable proofs (PCPs). This research aims at tackling a sequence of challenging open problems in PCP that include and generalize the Sliding Scale Conjecture of Bellare, Goldwasser, Lund and Russell from 1993. The latter conjecture is that a PCP verifier that uses r random bits can achieve soundness error that is exponentially small in r. Proving the conjecture will imply the first hardness results for polynomially large approximation factors. The other conjectures in the sequence, which consider special kinds of verifiers: projection, smooth, linear etc, imply more hardness of approximation results.

Proofs of PCP theorems often involve a large array of techniques: algebraic, combinatorial, information theoretic, coding theoretic and analytic. PI will employ and add to this toolbox. In particular, she will look into constructions of new low degree tests, composition methods, and amplification techniques for PCPs.

The broader impact contribution include the development of a comprehensive course in probabilistically checkable proofs, writing popular articles (e.g., about PCP), participation in the CS theory questions and answers website "CS Stack Exchange", and working with students of diverse backgrounds.

Project Start
Project End
Budget Start
2012-08-01
Budget End
2017-07-31
Support Year
Fiscal Year
2012
Total Cost
$492,256
Indirect Cost
Name
Massachusetts Institute of Technology
Department
Type
DUNS #
City
Cambridge
State
MA
Country
United States
Zip Code
02139