# ARC Colloquium, Madhur Tulsiani, Toyota Technological Institute at Chicago

Event Details
• Date/Time:
• Monday March 11, 2013
1:30 pm - 2:30 pm
• Location: Klaus 1116W
• Phone:
• URL:
• Email:
• Fee(s):
N/A
• Extras:
Contact

ndongi@cc.gatech.edu

Summaries

Summary Sentence: No summary sentence submitted.

Full Summary: No summary paragraph submitted.

Title: The Complexity of Somewhat Approximation Resistant Predicates

Abstract:

For 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.

Let \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.

Joint work with Subhash Khot and Pratik Worah.

In Campus Calendar
No
Groups
Invited Audience
No audiences were selected.
Categories
Seminar/Lecture/Colloquium
Keywords
No keywords were submitted.
Status
• Created By: Elizabeth Ndongi
• Workflow Status: Published
• Created On: Jan 29, 2013 - 4:27am
• Last Updated: Oct 7, 2016 - 10:02pm