Hardness of approximating the minimum distance of a linear code

DOI10.1109/TIT.2002.806118zbMath1063.68055OpenAlexW2169665116MaRDI 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)

Full work available at URL: https://doi.org/10.1109/tit.2002.806118

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Linear codes (general theory) (94B05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (21)

Smoothing out binary linear codes and worst-case sub-exponential hardness for LPN ⋮ The inapproximability of lattice and coding problems with preprocessing ⋮ Low-complexity weak pseudorandom functions in \(\mathtt{AC}0[\mathtt{MOD}2\)] ⋮ Squaring attacks on McEliece public-key cryptosystems using quasi-cyclic codes of even dimension ⋮ List-decoding Barnes-Wall lattices ⋮ NP-Hardness of Reed--Solomon Decoding, and the Prouhet--Tarry--Escott Problem ⋮ Sampling Graphs without Forbidden Subgraphs and Unbalanced Expanders with Negligible Error ⋮ On closest pair in Euclidean metric: monochromatic is as hard as bichromatic ⋮ Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH ⋮ The projection games conjecture and the hardness of approximation of Super-SAT and related problems ⋮ Restricted parameter range promise set cover problems are easy ⋮ A fuzzy vault scheme ⋮ On the De Boer-Pellikaan method for computing minimum distance ⋮ Algorithmic Problems for Metrics on Permutation Groups ⋮ As Close as It Gets ⋮ A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem ⋮ On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic ⋮ Parameterized complexity of small weight automorphisms and isomorphisms ⋮ Key masking using biometry ⋮ Minimal distance of propositional models ⋮ Unnamed Item

This page was built for publication: Hardness of approximating the minimum distance of a linear code