CAREER: New Directions in Inapproximability and Probabilistically Checkable Proofs

理论计算机科学研究的中心问题是：如何有效(快速)解决计算问题？虽然许多问题都有有效的算法，但有一大类重要的问题(称为NP-完全问题)不太可能有有效的算法。然而，在实践中，大致解决这些问题可能就足够了。本研究探讨是否能有效地找到NP完全问题的近似解，以及近似解的质量有多好。这项研究的主要贡献是否定的结果，即证明了对于某些NP-完全问题，有效地找到甚至是近似解是非常不可能的。为了说明证明这些否定结果的意义，调查者证明了它不太可能侵入某个密码系统，从而保证了其安全性不受恶意攻击。这项研究的另一个相关方面是概率可核对证明，这是一种为数学陈述指定证明格式的方法，因此可以非常有效地检查证明的有效性，只需查看证明中的几个地方，而不是阅读整个证明。这项研究有可能在科学研讨会、几个国际研究人员之间的合作、研究生课程的开发、促进本科生研究和为博士生提供建议方面产生更广泛的影响。理论和实践中出现的许多计算问题都是NP-完全问题。一种被广泛研究的处理NP-完备性的方法是设计计算近似最优解的多项式时间算法。然而，事实证明，对于许多问题，计算近似解本身就是一个NP-完全问题，这一著名的结果被称为PCP定理，发现于1992年。尽管在这一发现之后进行了大量的研究，但对于许多NP-完全问题，最著名的逼近结果和最著名的不可逼近结果之间存在差距。本研究致力于通过证明紧不可逼近结果来填补这一空白。PCP定理也可以被视为关于证明检查的结果(这就是它是如何被发现的)。它给出了一种为NP-语句指定证明的方法，从而可以非常有效地检查证明的有效性。这项研究调查了更有效的PCP的构造，并进一步应用于不可逼近结果。所开发的技术可能会在度量嵌入和学习理论等领域有新的应用。这项研究可能会在科学研讨会、国际研究人员之间的合作、研究生课程的开发、促进本科生研究和为博士生提供建议方面产生更广泛的影响。

The central question studied in theoretical computer science is: how efficiently (fast) can computational problems be solved?While many problems do have efficient algorithms, there is a wide class of important problems (called NP-complete problems) which are very unlikely to have efficient algorithms. In practice however, it may suffice to solve these problems approximately. This research investigates whether approximate solutions to NP-complete problems can be found efficiently, and how good is the quality of approximation. The main contribution of this research is negative results, i.e. proving that for certain NP-complete problems, efficiently finding even approximate solutions is very unlikely. To illustrate the significance of proving such negative results, the investigator proves that it is unlikely to break into a certain cryptosystem, giving a guarantee of its security against malicious attacks. Another related aspect of this research is Proababilistically Checkable Proofs, a method to specify proof formats for mathematical statements, such that the validity of the proof can be checked very efficiently, by looking at only a few places in the proof instead of reading the entire proof. The research has a potential for broader impact in terms of scientific workshops, collaboration between several international researchers, developement of graduate courses, promoting undergraduate research, and advising Ph.D. students. Many computational problems arising in theory and practice are NP-complete. An extensively studied approach to cope with NP-completeness is designing polynomial time algorithms that compute approximately optimal solutions. However, it turns out that for many problems, computing approximate solutions itself is an NP-complete problem, a famous result known as the PCP Theorem, discovered in 1992. In spite of the tremendous body of research that followed this discovery, for many NP-complete problems, there is a gap between the best known approximation result, and the best known inapproximability result. This research focusses on filling this gap by proving tight inapproximability results. The PCP Theorem can also be viewed as a result about proof checking (and that is how it was discovered). It gives a way of specifying proofs for NP-statements such that the validity of the proof can be checked very efficiently. The research investigates constructions of more efficient PCPs, with further applications to inapproximability results. The techniques developed are likely to have new applications to areas like metric embeddings and learning theory. The research has a potential for broader impact in terms of scientific workshops, collaboration between international researchers, developement of graduate courses, promoting undergraduate research and advising Ph.D. students.