[Colloquium] [Staff] Theory Seminars at Computer Science
Donna Brooms
donna at cs.uchicago.edu
Tue Nov 27 06:21:47 CST 2012
~REMINDER~
THEORY SEMINAR
November 27, 2012
3:00 p.m.
Ryerson 251
Pratik Worah
University of Chicago
www.cs.uchicago.edu/people/pworah
Title: The Complexity of Somewhat Approximation Resistant Predicates
Abstract: A boolean predicate $f:\{0,1\}^k\to\{0,1\}$ is said to be
{\em somewhat approximation resistant} if for some constant
$\tau > \frac{|f^{-1}(1)|}{2^k}$, given a $\tau$-satisfiable
instance of the MAX-$k$-CSP$(f)$ problem, it is NP-hard to find an
assignment that {\it strictly beats} the naive algorithm that
outputs a uniformly random assignment. Let $\tau(f)$ denote the
supremum over all $\tau$ for which this 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 {\it hardness gap} $(\tau(f) - \frac{|f^{-1}(1)|}{2^k})$ up to
a factor of $O(k^5)$.
We also give a similar characterization of the {\it integrality gap}
for the natural SDP relaxation of MAX-$k$-CSP$(f)$ after $\Omega(n)$
rounds of the Lasserre hierarchy.
Joint work with Subhash Khot (NYU and U. of Chicago) and
Madhur Tulsiani (TTI Chicago).
*Refreshments will be served prior to the talk at 2:30 in Ryerson 255*
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20121127/cb5f8921/attachment-0001.htm
More information about the Colloquium
mailing list