CS Events Monthly View

Qualifying Exam

Approximation and Hardness of Simultaneous and Covering CSPs


Download as iCal file

Friday, March 04, 2016, 11:00am


Constraint Satisfaction Problems (CSPs), which are ubiquitous in computer science, consist of a collection of constraints on small subsets of variables. In this talk, I will discuss two main results related to CSPs:

1. Simultaneous CSPs: Given a collection of instances of CSP on a same set of variables, can one find a single assignment to the variables that satisfies many constraints from each instance. In this work, we study the simultaneous CSPs and give a constant factor approximation algorithm for all k-CSPs and up to poly(log n) number of instances. We will also discuss some inapproximability results in this setting. This is a joint work with Swastik Kopparty and Sushant Sachdeva.

2. Covering CSPs: A set of assignments covers a given instance of CSP if for every constraint there exists at least one assignment in the set that satisfies the constraint. The minimum number of assignments that cover a given instance is called its covering number. In this talk, I will discuss about a characterization of inapproximability of the covering number based on a variant of Unique Games Conjecture.
This is a joint work with Prahladh Harsha and Girish Varma.

Speaker: Amey Bhangale



Location : Core A (Room 301)


Swastik Kopparty (advisor) , Shubhangi Saraf, Mario Szegedy and Ahmed Elgammal

Event Type: Qualifying Exam



Rutgers University