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

优化问题是np困难的，因此推测没有有效的算法，出现在人类知识的许多领域。重建系统发育、寻找市场均衡、航班调度和网络瓶颈检测都是这类问题的例子。算法专家通常能够设计出接近最优的有效算法。然而，对于许多问题，这种近似是相当粗糙的。此外，找到更好的近似值往往是np困难的。理解np困难问题的近似性与概率可检验证明（pcp）的深层理论密切相关。本研究旨在解决一系列具有挑战性的PCP开放问题，包括并推广Bellare， Goldwasser， Lund和Russell自1993年以来的滑动尺度猜想。后一个猜想是，使用r个随机比特的PCP验证器可以实现r中指数级小的稳健性误差。证明这个猜想将意味着多项式大的近似因子的第一硬度结果。序列中的其他猜想考虑了特殊类型的验证器：投影、光滑、线性等，这意味着近似结果的硬度更高。PCP定理的证明通常涉及大量的技术：代数、组合、信息论、编码论和分析。PI将使用并添加到这个工具箱中。特别是，她将研究新的低度测试，组成方法和pcp扩增技术的构建。更广泛的影响贡献包括开发一门关于概率可检验证明的综合课程，撰写流行文章（例如，关于PCP），参与CS理论问答网站“CS堆栈交换”，以及与不同背景的学生合作。

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.