TR99-029 Authors: Ilya Dumer, Daniele Micciancio, Madhu Sudan

Publication: 1st September 1999 10:04

Downloads: 1196

Keywords:

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^{(1 - \epsilon)} n}$, for any

$\epsilon > 0$, where $n$ denotes the block length of the code.

We also show that the minimum distance is not approximable

to within an additive error that is linear in the block

length of the code, unless NP equals RP.

Our results hold for codes over every finite field, including

the special case of binary codes. In the process we show that

the nearest codeword problem is hard to solve even under the

promise that the number of errors is (a constant factor) smaller

than the distance of the code (even if the code is asymptotically good).

This is a particularly meaningful version of the nearest codeword

problem.

Our results strengthen (though using stronger assumptions) a

previous result of Vardy who showed that the minimum

distance is NP-hard to compute exactly. Our results are obtained

by adapting proofs of analogous results for integer lattices due to

Ajtai and Micciancio.

A critical component in the adaptation is our use of

linear codes that perform better than random (linear) codes.