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

Sanjeev Arora

Princeton University

Friday, January 27, 2006
10:30am - SENSQ 5317

Refreshments at 10:00am

Hosted by Kirk Pruhs

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.

Brief Biography of Speaker

Sanjeev Arora is Professor of Computer Science at Princeton University. His research area is theoretical Computer Science, specifically, computational complexity, uses of randomness in computation, Probabilistically Checkable Proofs (PCPs), computing approximate solutions to NP-hard problems, and geometric embeddings of metric spaces.