The $k$-Even Set problem is a parameterized variant of the Minimum Distance Problem of linear codes over $\mathbb F_2$, which can be stated as follows: given a generator matrix $\mathbf A$ and an integer $k$, determine whether the code generated by $\mathbf A$ has distance at most $k$. Here, $k$ ... more >>>

The k-Even Set problem is a parameterized variant of the Minimum Distance Problem of linear codes over $\mathbb{F}_2$, which can be stated as follows: given a generator matrix A and an integer k, determine whether the code generated by A has distance at most k, or in other words, whether ... more >>>

We show that the nearest-codeword and minimum-distance problems for linear codes over every fixed finite field are W[1]-hard to approximate within any constant factor under deterministic fixed-parameter many-one reductions. This gives unconditional deterministic parameterized inapproximability for minimum distance, including the binary problem usually called Even Set. The reduction starts from ... more >>>