AF: Small: Sliding Scale Problems in Probabilistic Checking of Proofs

点击翻译按钮获取中文摘要

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.