BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Isaac Newton Institute Seminar Series
SUMMARY:Unconditional Hardness of Approximation - Anuj Daw
ar (University of Cambridge)
DTSTART;TZID=Europe/London:20220607T111500
DTEND;TZID=Europe/London:20220607T121500
UID:TALK174797AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/174797
DESCRIPTION:For many NP-hard optimization problems it is known
that\, unless P = NP\, no polynomial-time algorit
hm can give an approximate solution guaranteed to
be within a fixed constant factor of the optimum.
\;We are able to show\, in several such cases
\, and without any complexity theoretic assumption
\, that no algorithm that is expressible in counti
ng logic (i.e. no symmetric algorithm in a general
sense) can compute an approximate solution. Since
important algorithmic techniques for approximatio
n algorithms (such as linear or semidefinite progr
amming) are expressible in counting logic\, this y
ields lower bounds on what can be achieved by such
methods. The results are established by showing i
nseparability in the logic of instances with a hig
h optimum from those with a low optimum. \;Th
ese instances are obtained by sampling from a suit
able random distribution.\nThis is joint work with
Albert Atserias (UPC\, Barcelona)\n \;
LOCATION:Seminar Room 1\, Newton Institute
CONTACT:
END:VEVENT
END:VCALENDAR