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):
  • Extras:


Summary Sentence: No summary sentence submitted.

Full Summary: No summary paragraph submitted.

Title: The Complexity of Somewhat Approximation Resistant Predicates


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.


Additional Information

In Campus Calendar

College of Computing, School of Computer Science, ARC

Invited Audience
No audiences were selected.
No keywords were submitted.
  • Created By: Elizabeth Ndongi
  • Workflow Status: Published
  • Created On: Jan 29, 2013 - 4:27am
  • Last Updated: Oct 7, 2016 - 10:02pm