CAREER: New Directions in Inapproximability and Probabilistically Checkable Proofs

New York University, New York NY

Investigators

Abstract

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.