University of Cambridge > > Isaac Newton Institute Seminar Series > Unconditional Hardness of Approximation

Unconditional Hardness of Approximation

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

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.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


© 2006-2024, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity