Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



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