When are how can we compute approximate solutions to NP-hard problems?
Fine 214 Wenesday Nov.6th 6:00pm
In the 1970s it was discovered that many computational problems in a variety of disciplines are NP-complete: they do not have efficient algorithms if P != NP, as is widely believed. This was a profound discovery. However, in practice it often suffices to solve problems approximately: say, to obtain a solution of cost within 10% of optimum. Can efficient algorithms find approximately optimal solutions? Research in the past two decades has answered the approximability issue for a large subset of NP-complete problems. We know the precise approximation threshold that can be achieved by efficient algorithms, and also know that improving upon that threshold is no easier than exact optimization. The former is the domain of “approximation algorithms,” and the latter of the theory of “probabilistically checkable proofs.” This theory makes connections with a host of other disciplines and yields surprising results such as the PCP Theorem, which states that mathematical proofs can be checked by examining a constant number of bits in them (this constant is independent of the size of the proof).
(The talk will be geared to a general audience.)
Speaker bio: Sanjeev Arora is Charles C. Fitzmorris Professor of Computer Science at Princeton University. His research area spans several areas of theoretical Computer Science. He has received the ACM-EATCS Gödel Prize (in 2001 and 2010), Packard Fellowship (1997), the ACM Infosys Foundation Award in the Computing Sciences (2012), the Fulkerson Prize (2012), the Simons Investigator Award (2012). He served as the founding director for the Center for Computational Intractability at Princeton.
