[Colloquium] Talks at TTIC: Friday, November 22nd - Madhur Tulsiani

[Dawn Ellis]

*This will be the last research talk for the year; we will resume on
January 10th.  Thank you for your continued support of the TTIC Faculty.*

When:     Friday, November 22nd at Noon

Where:    TTIC, 6045 S Kenwood Avenue, 5th Floor, Room #526

Who:       TTIC Faculty, Madhur Tulsiani

Title:       A Characterization of Approximation Resistance

Abstract:

An instance of a Constraint Satisfaction Problem over Boolean variables
with an underlying predicate f:{-1,1}^k -> {0,1} is specified by (say) m
constraints over (say) n variables, with each constraints given by f
applied to some k-tuple of (possibly negated) variables. A predicate
f:{-1,1}^k -> {0,1} with \rho(f) = \frac{|f^{-1}(1)|}{2^k} is called
approximation resistant if given a near-satisfiable instance of CSP(f), it
is computationally hard to find an assignment that satisfies at least
\rho(f)+\Omega(1) fraction of the constraints.

We present a complete characterization of approximation resistant
predicates under the Unique Games Conjecture. We also present
characterizations in the mixed linear and semi-definite programming
hierarchy and the Sherali-Adams linear programming hierarchy. In the former
case, the characterization coincides with the one based on UGC. Each of the
two characterizations is in terms of existence of a probability measure
with certain symmetry properties on a natural convex polytope associated
with the predicate.

Joint work with Subhash Khot and Pratik Worah.

***************************************
Research at TTIC Seminar Series

TTIC is hosting a weekly seminar series presenting the research currently
underway at the Institute. Every week a different TTIC faculty member will
present their research.  The lectures are intended both for students
seeking research topics and adviser, and for the general TTIC and
University of Chicago communities interested in hearing what their
colleagues are up to.

To receive announcements about the seminar series, please subscribe to the
mailing list: https://groups.google.com/a/ttic.edu/group/talks/subscribe

Speaker details can be found at: http://www.ttic.edu/tticseminar.php.

For additional questions, please contact David McAllester at
mcallester at ttic.edu


-- 
*Dawn Ellis*
Administrative Coordinator,
Bookkeeper
773-834-1757
dellis at ttic.edu

TTIC
6045 S. Kenwood Ave.
Chicago, IL. 60637
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20131115/1840e2ef/attachment.htm