Covering CSPs

SHARE:

Event Speaker: 

Irit Dinur, Weizmann and Harvard

Event Location: 

32-124

Event Date/Time: 

Tuesday, October 30, 2012 - 4:15pm

Research Area: 

Covering CSPs

Speaker: Irit Dinur, Weizmann and Harvard
Date: Tuesday, October 30 2012
Time: 4:15PM to 5:15PM
Refreshments: 3:45PM
Location: 32-124
Host: Dana Moshkovitz, CSAIL, MIT
Contact: Be Blackburn, 3-6098, imbe@mit.edu

 

We study the complexity of constraint satisfaction problems (CSPs) from a new "covering" perspective. We define the covering number of a CSP instance C, denoted v(C), to be the smallest number of assignments to the variables, such that each constraint is satisfied by at least one of the assignments. This covering notion describes situations in which we must satisfy all the constraints, and are willing to use more than one assignment to do so. At the same time, we want to minimize the number of assignments. We study the covering CSP problem for different constraint predicates. We also study an interesting relationship between this problem and approximate coloring of graphs. Based on joint work with Gillat Kol.

 

See other events that are part of Theory Colloquium 2012/2013

See other events happening in October 2012