BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Unconditional Hardness of Approximation - Anuj Dawar (University o
 f Cambridge)
DTSTART:20220607T101500Z
DTEND:20220607T111500Z
UID:TALK174797@talks.cam.ac.uk
DESCRIPTION:For many NP-hard optimization problems it is known that\, unle
 ss P = NP\, no polynomial-time algorithm can give an approximate solution 
 guaranteed to be within a fixed constant factor of the optimum. &nbsp\;We 
 are able to show\, in several such cases\, and without any complexity theo
 retic assumption\, that no algorithm that is expressible in counting logic
  (i.e. no symmetric algorithm in a general sense) can compute an approxima
 te solution. Since important algorithmic techniques for approximation algo
 rithms (such as linear or semidefinite programming) are expressible in cou
 nting logic\, this yields lower bounds on what can be achieved by such met
 hods. The results are established by showing inseparability in the logic o
 f instances with a high optimum from those with a low optimum. &nbsp\;Thes
 e instances are obtained by sampling from a suitable random distribution.\
 nThis is joint work with Albert Atserias (UPC\, Barcelona)\n&nbsp\;
LOCATION:Seminar Room 1\, Newton Institute
END:VEVENT
END:VCALENDAR