COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. |

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

## Unconditional Hardness of ApproximationAdd 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. |
## Other liststhehealthcareguardian Trinity College Cambridge public events Quantitative Climate and Environmental Science Seminars## Other talksStatistics Clinic Summer 2022 III Oral Session 2 Intermittency in turbulence and the 3D Navier-Stokes regularity problem - virtual talk Session 1 of ECR Showcase Akilesh Verma title and abstract tba Welcome and Introduction |