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 > On the usefulness of predicates

## On the usefulness of predicatesAdd to your list(s) Download to your calendar using vCal - Hstad, J (KTH NADA)
- Tuesday 29 March 2011, 14:00-15:00
- Seminar Room 1, Newton Institute.
If you have a question about this talk, please contact Mustapha Amrani. Discrete Analysis One successful application of discrete harmonic analysis has been the analysis of Max-CSPs, maximum constraint satisfaction problems. In the Max-CSP defined by a predicate P of arity k we are presented with a list of k-tupels of literals and the goal is to find assignments to the variables in order to maximize the number of resulting k-bit strings that satisfy P. A predicate P is approximation resistant if, even for instances where the optimal assignments satisfies (almost) all constraints, it is infeasible to do find an assignment that satisfies substantially more constraints than what is obtained by picking a random assignment. We study a more general question of given the promise of the existence of an assignment that satisfies all the constraints given by P, to efficiently finding an assignment that satisfies a weaker predicate (or more general function) Q. In particular we say P is useless if it is infeasible to do substantially better than random for any Q. In this talk we describe this framework and derive results on uselessness based on NP ≠ P and the Unique Games Conjecture. 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 listsPeter Whittle Lecture Partial Differential Equations seminar Wolfson Research Event 2016## Other talksThermodynamics de-mystified? /Thermodynamics without Ansätze? Bank credit rating changes, capital structure adjustments and lending Quantum geometry from the quantisation of gravitational boundary modes on a null surface Laser Printed Organic Electronics, Metal-Organic Framework - Polymer Nanofiber Composites for Gas Separation Ribosome profiling and virus infection Mothers & Daughters: a psychoanalytical perspective 'Politics in Uncertain Times: What will the world look like in 2050 and how do you know? Computing knot Floer homology Fumarate hydratase and renal cancer: oncometabolites and beyond The ‘Easy’ and ‘Hard’ Problems of Consciousness |