时间：5月16日晚上6:30

地点：紫金港CAD&CG 402会议室

题目：When and how can we compute approximate solutions to intractable problems

摘要：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).

报告者简介：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.