**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 1MDC has input a code and output .

NCP has input a code and a point and output

**2. History **

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.

**4. Proof **

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 , , .

** References **

[ABSS] Sanjeev Arora, Laszlo Babai, Jacques Stern and Z Sweedyk; * Hardness of Approximate Optima in Lattices, Codes, and Linear Systems.* FOCS 1993.