BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Isaac Newton Institute Seminar Series
SUMMARY:On the usefulness of predicates - Hstad\, J (KTH N
ADA)
DTSTART;TZID=Europe/London:20110329T140000
DTEND;TZID=Europe/London:20110329T150000
UID:TALK30441AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/30441
DESCRIPTION:One successful application of discrete harmonic an
alysis has been the analysis of Max-CSPs\, maximum
constraint satisfaction problems. \n\nIn the Max-
CSP defined by a predicate P of arity k we are pre
sented with a list of k-tupels of literals and the
goal is to find assignments to the variables in o
rder to maximize the number of resulting k-bit str
ings that satisfy P. \n\nA predicate P is approxim
ation resistant if\, even for instances where the
optimal assignments satisfies (almost) all constra
ints\, it is infeasible to do find an assignment t
hat satisfies substantially more constraints than
what is obtained by picking a random assignment. \
n\nWe study a more general question of given the p
romise of the existence of an assignment that sati
sfies all the constraints given by P\, to efficien
tly finding an assignment that satisfies a weaker
predicate (or more general function) Q. \n\nIn par
ticular we say P is useless if it is infeasible to
do substantially better than random for any Q. \n
\nIn this talk we describe this framework and deri
ve results on uselessness based on NP &ne\; P and
the Unique Games Conjecture.\n
LOCATION:Seminar Room 1\, Newton Institute
CONTACT:Mustapha Amrani
END:VEVENT
END:VCALENDAR