Theory Seminar, November 15th, 12:20pm
Warren Weaver Hall, Room 1314

Covering CSPs
Gillat Kol, Wiezmann Institute

We study the covering complexity of constraint satisfaction problems (CSPs). The covering number of a CSP instance is 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 (as opposed to max-CSP, where we restrict ourselves to a single assignment). At the same time, we want to minimize the number of assignments. We study the covering problem for different constraint predicates, and give a partial characterization of covering-hard predicates. Joint work with Irit Dinur.