Title :
Hardness of approximating the minimum distance of a linear code
Author :
Micciancio, Daniele ; Dumer, Ilya ; Sudan, Madhu
Author_Institution :
Dept. of Comput. Sci. & Eng., California Univ., San Diego, La Jolla, CA, USA
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 NP equals RP. In the process we show that it is hard to find the nearest codeword even if the number of errors exceeds d/2 by an arbitrarily small fraction εd
Keywords :
computational complexity; linear codes; polynomial approximation; NP-hardness; linear code; minimum distance; nearest codeword; random polynomial time; Computer science; Decoding; Educational institutions; Engineering profession; Lattices; Linear code; Polynomials; Quadratic programming; Random number generation; Vectors;
Conference_Titel :
Information Theory, 2000. Proceedings. IEEE International Symposium on
Conference_Location :
Sorrento
Print_ISBN :
0-7803-5857-0
DOI :
10.1109/ISIT.2000.866550
