BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:On the usefulness of predicates - Hstad\, J (KTH NADA)
DTSTART:20110329T130000Z
DTEND:20110329T140000Z
UID:TALK30441@talks.cam.ac.uk
CONTACT:Mustapha Amrani
DESCRIPTION:One successful application of discrete harmonic analysis has b
 een the analysis of Max-CSPs\, maximum constraint satisfaction problems. \
 n\nIn the Max-CSP defined by a predicate P of arity k we are presented wit
 h a list of k-tupels of literals and the goal is to find assignments to th
 e variables in order to maximize the number of resulting k-bit strings tha
 t satisfy P. \n\nA predicate P is approximation resistant if\, even for in
 stances where the optimal assignments satisfies (almost) all constraints\,
  it is infeasible to do find an assignment that satisfies substantially mo
 re constraints than what is obtained by picking a random assignment. \n\nW
 e study a more general question of given the promise of the existence of a
 n assignment that satisfies all the constraints given by P\, to efficientl
 y finding an assignment that satisfies a weaker predicate (or more general
  function) Q. \n\nIn particular we say P is useless if it is infeasible to
  do substantially better than random for any Q. \n\nIn this talk we descri
 be this framework and derive results on uselessness based on NP &ne\; P an
 d the Unique Games Conjecture.\n
LOCATION:Seminar Room 1\, Newton Institute
END:VEVENT
END:VCALENDAR