Approximation and Hardness of Simultaneous and Covering CSPs
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