Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > W[1]-HARDNESS:
Reports tagged with W[1]-hardness:
TR26-234 | 8th October 2026
Venkatesan Guruswami, Xuandi Ren

Deterministic Parameterized Inapproximability of Nearest Codeword and Minimum Distance

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 >>>




ISSN 1433-8092 | Imprint