Hardness of approximating the minimum distance of a linear code
- 14 January 2003
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 49 (1) , 22-37
- https://doi.org/10.1109/tit.2002.806118
Abstract
We show that the minimum distance d of a linear code is not approximable to within any constant factor in random polynomial time (RP), unless nondeterministic polynomial time (NP) equals RP. We also show that the minimum distance is not approximable to within an additive error that is linear in the block length n of the code. Under the stronger assumption that NP is not contained in random quasi-polynomial time (RQP), we show that the minimum distance is not approximable to within the factor 2/sup log1-/spl epsi//(n), for any /spl epsi/>0. Our results hold for codes over any finite field, including binary codes. In the process, we show that it is hard to find approximately nearest codewords even if the number of errors exceeds the unique decoding radius d/2 by only an arbitrarily small fraction /spl epsi/d. We also prove the hardness of the nearest codeword problem for asymptotically good codes, provided the number of errors exceeds (2/3)d. Our results for the minimum distance problem strengthen (though using stronger assumptions) a previous result of Vardy (1997) who showed that the minimum distance cannot be computed exactly in deterministic polynomial time (P), unless P = NP. Our results are obtained by adapting proofs of analogous results for integer lattices due to Ajtai (1998) and Micciancio (see SIAM J. Computing, vol.30, no.6, p.2008-2035, 2001). A critical component in the adaptation is our use of linear codes that perform better than random (linear) codes.Keywords
This publication has 15 references indexed in Scilit:
- The inapproximability of lattice and coding problems with preprocessingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Complexity of Lattice ProblemsPublished by Springer Nature ,2002
- Some optimal inapproximability resultsJournal of the ACM, 2001
- Bounds on list decoding of MDS codesIEEE Transactions on Information Theory, 2001
- The Shortest Vector in a Lattice is Hard to Approximate to within Some ConstantSIAM Journal on Computing, 2001
- Clique is hard to approximate within n1−εActa Mathematica, 1999
- The Hardness of Approximate Optima in Lattices, Codes, and Systems of Linear EquationsJournal of Computer and System Sciences, 1997
- The hardness of decoding linear codes with preprocessingIEEE Transactions on Information Theory, 1990
- Two theorems on random polynomial timePublished by Institute of Electrical and Electronics Engineers (IEEE) ,1978
- On the inherent intractability of certain coding problems (Corresp.)IEEE Transactions on Information Theory, 1978