Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR26-234 | 8th October 2026 17:42

Deterministic Parameterized Inapproximability of Nearest Codeword and Minimum Distance

RSS-Feed

Abstract:

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 exact nearest codeword and produces a constant gap directly. Over $\mathbb{F}_q$ with $q>2$, an input of length $m$ and threshold $k$ gives instances with threshold $q^k$ and length $O_q(q^k m)$. Tensor products amplify the gap, and a simple concatenation handles codes over $\mathbb{F}_2$.



ISSN 1433-8092 | Imprint