ARC Colloquium: Pratik Worah - New York University

Event Details
  • Date/Time:
    • Wednesday February 26, 2014
      12:30 pm
  • Location: MiRC 102A
  • Phone:
  • URL:
  • Email:
  • Fee(s):
  • Extras:


Summary Sentence: CSPs, Approximation Resistance, and Optimization Hierarchies

Full Summary: No summary paragraph submitted.

Title: CSPs, Approximation Resistance, and Optimization Hierarchies


A k-ary boolean predicate f, naturally implies a canonical constraint satisfaction problem (CSP(f)). Let MAX k-CSP(f) denote the problem of finding the maximum fraction of simultaneously satisfiable constraints in any given instance of CSP(f). A trivial randomized algorithm achieves an approximation factor proportional to f^{-1}(1).

 On the other hand, it is known, for some f, that an efficient algorithm can not perform strictly better than the trivial algorithm - such f are known as approximation resistant.

 One of the main problems in this area is to characterize which predicates are approximation resistant.

 In this talk, I will survey known bounds for CSPs and their connections with LP and SDP hierarchies. Finally, I will give an overview of my recent research in this area, which gives a characterization of approximation resistance.

 (Joint with S.Khot and M.Tulsiani).

Additional Information

In Campus Calendar

College of Computing, School of Computer Science, ARC

Invited Audience
Undergraduate students, Faculty/Staff, Graduate students
No keywords were submitted.
  • Created By: Elizabeth Ndongi
  • Workflow Status: Published
  • Created On: Feb 14, 2014 - 11:01am
  • Last Updated: Apr 13, 2017 - 5:23pm