Hardness of approximating the minimum distance of a linear code
From MaRDI portal
Publication:4679877
DOI10.1109/TIT.2002.806118zbMath1063.68055MaRDI QIDQ4679877
Madhu Sudan, Daniele Micciancio, I. I. Dumer
Publication date: 31 May 2005
Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)
68Q25: Analysis of algorithms and problem complexity
94B05: Linear codes (general theory)
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68W25: Approximation algorithms
Related Items
Algorithmic Problems for Metrics on Permutation Groups, A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem, Squaring attacks on McEliece public-key cryptosystems using quasi-cyclic codes of even dimension, Key masking using biometry, On the De Boer-Pellikaan method for computing minimum distance, The inapproximability of lattice and coding problems with preprocessing, Restricted parameter range promise set cover problems are easy, List-decoding Barnes-Wall lattices, A fuzzy vault scheme, As Close as It Gets