[Lowerbounds, Upperbounds]

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

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.

I think we should make an active effort to avoid scheduling speakers from abroad to give talks in the last session, or perhaps even the one before that. I don’t know if this is entirely possible, but I feel bad when a fellow researcher, having flown all the way from half a globe away, has to give the last talk with a mostly empty room.

I know someone has to be in the last session. So yes, I will volunteer if we are to prevent this from happening again. My guess is that many of us in the community share this view too.

Imagine what can happen at the US border when you invite a speaker from a foreign country…

[T]he customs agents concluded that because Microsoft was covering my flight and accommodation, I was being compensated for consulting activities. In order to enter the country, I’d need a work permit.

http://www.darrenbarefoot.com/archives/2006/01/im-an-alien-an-illegal-alien.html

P.S. I don’t expect any speakers from the academic will have this problem, or so I hope.