CSAIL Event Calendar
Covering CSPsSpeaker: 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  
|