BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:When and how can we compute approximate solutions to NP-hard probl
 ems?
DTSTART:20130607T111500
DTEND:20130607T121500
DTSTAMP:20260407T064511Z
UID:0c919e7d9105cde6fbe14e65e659e30a4b8e07229edf5c9d0376017f
CATEGORIES:Conferences - Seminars
DESCRIPTION:Prof. Sanjeev Arora\, Princeton University\nCan efficient algo
 rithms find approximately optimal solutions (provably) to NP-hard problems
 ? This question has animated a big research effort in theoretical CS in th
 e past few decades. This included the PCP Theorems and many exciting appro
 ximation algorithms. \nFor several problems we even know the precise appr
 oximation threshold that can be achieved by efficient algorithms\, and als
 o know that improving upon that threshold is no easier than exact optimiza
 tion. This theory makes connections with a host of other disciplines. Even
  the PCP Theorem (which says that proofs can be probabilistically checked 
 by examining a constant number of bits in them) seems at first sight to ha
 ve nothing to do with approximation. This talk\, which is geared to a broa
 d scientific audience\, will survey this field.
LOCATION:BC 420 https://plan.epfl.ch/?room==BC%20420
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR