scientific article; zbMATH DE number 503206

MaRDI QIDQ4279529zbMATHFDO

Authors Jacques Stern

Publication date 17 February 1994

zbMATH Keywords

Hamming distancedecoding algorithmsinteger lattices\({\mathcal N}{\mathcal P}\)-completeness

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Linear codes (general theory) (94B05)

Recommendations

• Hardness of approximating the minimum distance of a linear code
• The intractability of computing the minimum distance of a code
• Some new NP-complete coding problems
• The Parametrized Complexity of Some Fundamental Problems in Coding Theory

Cited in

(3)

• Randomized decoding of Gabidulin codes beyond the unique decoding radius
• The hardness of approximate optima in lattices, codes, and systems of linear equations
• Parameterized intractability of even set and shortest vector problem from Gap-ETH

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4279529)