Why NP got a new definition: the quest to understand the approximation properties of NP-hard optimization problems

Abstract: Thousands of optimization problems in a variety of application areas are known to be NP-hard. Since no efficient exact algorithm is known, researchers have tried to understand the complexity of computing approximately optimal solutions. Surprisingly, NP-complete problems differ a lot in this respect. This talk is a survey of the many exciting results proved in the last 15 years in the quest to understand this phenomenon. The first type of result shows nonapproximability: for many problems, computing approximate solutions is no easier than computing optimal solutions. This is shown by proving a new probabilistic characterization of NP, according to which it is possible to check certificates for membership in an NP language by examining a constant number of bits in the certificate. We will survey this result (the so-called PCP Theorem) and its many extensions. The other type of result consists of designing better approximation algorithms. This endeavor has also been successful for many problems, and a large body of techniques has been developed in the past decade. We will survey some of these. The talk will be self-contained.

Speaker's Bio: Sanjeev Arora is Professor of Computer Science at Princeton University and works in computational complexity theory, approximation algorithms for NP-hard problems, geometric algorithms, and probabilistic algorithms. He has received the ACM Dissertation Prize, the SIGACT-EATCS Goedel Prize, and the Packard Fellowship.