Hardness of approximating the minimum distance of a linear code
| Author(s) : | Daniele Micciancio Ilya Dumer, |
| Publisher : | N/A |
| Publication Date : | 1999 |
| ISSN : | N/A |
| Abstract : | We show that the minimum distance of a linear code (or equivalently, the weight of the lightest codeword) is not approximable to within any constant factor in random polynomial time (RP), unless NP equals RP. Under the stronger assumption that NP is not contained in RQP (random quasi-polynomial time), we show that the minimum distance is not approximable to within the factor 2 log, |