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.

 

Additional Information

In Campus Calendar
No
Groups

College of Computing, School of Computer Science, ARC

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