Skip to content Skip to navigation
Qualifying Exam
3/4/2016 11:00 am
Core A (Room 301)

Approximation and Hardness of Simultaneous and Covering CSPs

Amey Bhangale, Rutgers University

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

Abstract

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.