Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > PCP, UNIQUE GAMES CONJECTURE, HYPERGRAPH COLORING:
Reports tagged with PCP, Unique Games Conjecture, Hypergraph Coloring:
TR12-088 | 7th July 2012
Irit Dinur, Gillat Kol

#### Covering CSPs

We study the covering complexity of constraint satisfaction problems (CSPs). The covering number of a CSP instance C, denoted $\nu(C)$, 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 ... more >>>

ISSN 1433-8092 | Imprint