Unconditional Hardness of Approximation

Add to your list(s) Download to your calendar using vCal

• Anuj Dawar (University of Cambridge)
• Tuesday 07 June 2022, 11:15-12:15
• Seminar Room 1, Newton Institute.

If you have a question about this talk, please contact nobody.

SASW09 - International conference on computability, complexity and randomness

For many NP-hard optimization problems it is known that, unless P = NP, no polynomial-time algorithm 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 counting logic (i.e. no symmetric algorithm in a general sense) can compute an approximate solution. Since important algorithmic techniques for approximation algorithms (such as linear or semidefinite programming) are expressible in counting logic, this yields lower bounds on what can be achieved by such methods. The results are established by showing inseparability in the logic of instances with a high optimum from those with a low optimum.  These instances are obtained by sampling from a suitable random distribution. This is joint work with Albert Atserias (UPC, Barcelona)  

This talk is part of the Isaac Newton Institute Seminar Series series.

This talk is included in these lists:

• All CMS events
• Featured lists
• INI info aggregator
• Isaac Newton Institute Seminar Series
• School of Physical Sciences
• Seminar Room 1, Newton Institute
• bld31

Note that ex-directory lists are not shown.