Approximating distance of linear codes
1. Linear codes
A linear code is a linear subspace in a finite dimensional vector space over a finite field . In this course, the field will be .
The distance of the code is
For applications, it is important that be large while be not too small. Also, it is necessary, given an arbitrary point , to be able to compute the point of which is nearest to . Here we focus on two computational problems.
Definition 1 MDC has input a code and output .
NCP has input a code and a point and output
BMvT 1978: NCP is NP-hard Arora Babai Stern Sweedyk 1993: NCP is NP-hard to approximate within any constant factor, [ABSS].
V 1997: MDC is NP-hard. DMS 1999: MDC is hard to approximate within any constant, assuming NPRP. Chen-Wang 2009: MDC is NP-hard to approximate within any constant (i.e. they derandomize the previous reduction).
Best known algorithm for MDC has an approximation ratio of , subconstant (Berman Karpinski 2002).
3. New results
Subhash Khot and I give a simplified proof of Chen and Wang’s theorem and prove hardness for a subclass of asymptotically good codes, i.e. on which , stay bounded away from .
Linial: can one prove hardness on smaller classes having nice properties like unique minimum point ? Answer: not yet.
Question: Is there an -approximation algorithm, for some ? In other words, knowing that , output of algorithm is .
Question: Is there -hardness for MDC ? This is known (Håstad) for NCP.
The starting point of our reduction is the MAX NAND problem.
- Input: boolean variables, constraints of the form ().
- Output: an assignment of variables
- Objective: maximize number of satisfied equations.
PCP theorem implies that such that MAX NAND is -inapproximable. Indeed, arbitrary -ary constraints reduce to sets of Nand equations.
4.1. Step 1: Reduce MAX NAND to NCP
To a NAND instance, there is a bipartite graph attached. Left hand vertices correspond to variables, right hand vertices to constraints, each of them connected to its three variables. Let , .
Next we create a -dimensional vectorspace over as follows. There is one coordinate, still denoted , for each variable, and 4 coordinates for each constraints. Our intention is that these coordinates represent characteristic functions of elements of , one for each constraint .
These equations define an affine subspace in . Ignoring the last variables turns it into a subspace of .
Claim: If our MAX NAND instance has , then
Thus the linear space parallel to is a hard NPC instance.
4.2. Step 2: Extend to MDC
For this, one must replace with a linear (and not affine) space. Replace constant in (0) by a variable . If , we are done by previous analysis. If , we are in a big trouble.
Attempt: construct a dummy NAND instance such that if we apply reduction to , then any codeword which has must have large weight. Then apply reduction to .
This instance has variables , and constraints . We fix a linear code , and impose extra constraints that , , .