Skip to content



On the usefulness of predicates

Håstad, J (KTH NADA)
Tuesday 29 March 2011, 14:00-15:00

Seminar Room 1, Newton Institute


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.


The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.

Back to top ∧