Parameterized Inapproximability of Exact Cover and Nearest Codeword

Venkatesan Guruswami, Patrick Lin

The $k$-ExactCover problem is a parameterized version of the ExactCover problem, in which we are given a universe $U$, a collection $S$ of subsets of $U$, and an integer $k$, and t…