scientific article; zbMATH DE number 503206

MaRDI QIDQ4279529zbMATH OpenFDO

Authors Jacques Stern

Publication date 17 February 1994

zbMATH Keywords

\({\mathcal N}{\mathcal P}\)-completenessdecoding algorithmsHamming distanceinteger lattices

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

(4)

• 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
• Randomized decoding of Gabidulin codes beyond the unique decoding radius
• Improved lower bounds for approximating parameterized nearest codeword and related problems under 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)