BEGIN:VCALENDAR
PRODID:-//Mercury//HGEvent//EN
VERSION:2.0
METHOD:PUBLISH
BEGIN:VEVENT
STATUS:CONFIRMED
LAST-MODIFIED:20130521T091510
PRIORITY:0
CLASS:PUBLIC
UID:ATEvent-eed436ece7e23bbcfe0d4623c4969225
SUMMARY:ARC Colloquium\, Madhur Tulsiani\, Toyota Technological Institute at Chicago
DESCRIPTION:Title: The Complexity of Somewhat Approximation Resistant Predicates\nAbstract:\nFor a Boolean predicate f on k variables\, let \rho(f) be the probability that a constraint of the form f(x_1\,...\,x_k) is satisfied by a random assignment. A predicate f is called "somewhat approximation resistant" if for some constant \tau > \rho(f)\, given a \tau-satisfiable instance of the Max-k-CSP(f) problem\, it is NP-hard to find an assignment that strictly beats the naive algorithm that outputs a uniformly random assignment.\nLet \tau(f) denote the supremum over all \tau for which the above holds. It is known that a predicate is somewhat approximation resistant precisely when its Fourier degree is at least 3. For such predicates\, we give a characterization of the "hardness gap" (\tau(f) -\rho(f)) up to a factor of O(k^5). We also give a similar characterization of the integrality gap for the natural SDP relaxation of Max-k-CSP after \Omega(n) rounds of the Lasserre hierarchy.\nJoint work with Subhash Khot and Pratik Worah.\n \n
DTSTART:20130311T133000
DTEND:20130311T143000
CREATED:20130304T221513
DTSTAMP:20130304T221513
SEQUENCE:0
LOCATION:
END:VEVENT
END:VCALENDAR