## Notes of Per Austrin’s talk, jan. 20

Approximating distance of linear codes

1. Linear codes

A linear code is a linear subspace ${C}$ in a finite dimensional vector space ${\mathbf{F}^n}$ over a finite field ${\mathbf{F}}$. In this course, the field will be ${\mathbf{F}_2}$.

The distance of the code is

$\displaystyle \begin{array}{rcl} d(C)=\frac{1}{n}\min_{x,\not=y\in C} |x-y|_{1}. \end{array}$

For applications, it is important that ${\mathrm{dim}(C)}$ be large while ${d(C)}$ be not too small. Also, it is necessary, given an arbitrary point ${p\in\mathbf{F}_2^n}$, to be able to compute the point of ${C}$ which is nearest to ${p}$. Here we focus on two computational problems.

Definition 1 MDC has input a code ${C}$ and output ${d(C)}$.

NCP has input a code ${C}$ and a point ${p\in\mathbf{F}_2^n}$ and output

$\displaystyle \begin{array}{rcl} d(p,C)=\frac{1}{n}\min_{x\in C}|x-p|. \end{array}$

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 NP${\not:}$RP. 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 ${\frac{\epsilon k}{\log k}}$, ${\epsilon}$ 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 ${r(C)}$, ${d(C)}$ stay bounded away from ${0}$.

Linial: can one prove hardness on smaller classes having nice properties like unique minimum point ? Answer: not yet.

Question: Is there an ${(\epsilon,\epsilon^t)}$-approximation algorithm, for some ${t>0}$ ? In other words, knowing that ${d(C)<\epsilon}$, output of algorithm is ${<\epsilon^t}$.

Question: Is there ${(\epsilon,\frac{1}{2}-\epsilon)}$-hardness for MDC ? This is known (Håstad) for NCP.

4. Proof

The starting point of our reduction is the MAX NAND problem.

• Input: ${n}$ boolean variables, ${m}$ constraints of the form ${x_k =NAND(x_i ,x_j)}$ (${=x_i x_j +1}$).
• Output: an assignment of variables
• Objective: maximize number of satisfied equations.

PCP theorem implies that ${\exists\delta>0}$ such that MAX NAND is ${(1,1-\delta)}$-inapproximable. Indeed, arbitrary ${3}$-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 ${R=4}$, ${[4]=Nand^{-1}(1)=\{001,011, 101, 110\}}$.

Next we create a ${4m+n}$-dimensional vectorspace over ${\mathbf{F}_2}$ as follows. There is one coordinate, still denoted ${x_i}$, for each variable, and 4 coordinates for each constraints. Our intention is that these coordinates represent characteristic functions ${S_{c}: \{001,011, 101, 110\}\rightarrow\mathbf{F}_2}$ of elements of ${Nand^{-1}(1)}$, one for each constraint ${c}$.

Such functions would satisfy

$\displaystyle \begin{array}{rcl} \sum_{\gamma\in[4]}S_{c}(\gamma)=1,\quad \sum_{\gamma\in[4]}\gamma_i S_{c}(\gamma)=x_i \textrm{ for the 3 variables in }c. \end{array}$

These equations define an affine subspace in ${\mathbf{F}_2^{n+4m}}$. Ignoring the last ${n}$ variables turns it into a subspace ${\mathcal{S}}$ of ${\mathbf{F}_2^{4m}}$.

Claim: If our MAX NAND instance has ${OPT=1-\epsilon}$, then

$\displaystyle \begin{array}{rcl} \min_{p\in\mathcal{S}}|p|=m(1+2\epsilon). \end{array}$

Thus the linear space parallel to ${\mathcal{S}}$ is a hard NPC instance.

4.2. Step 2: Extend to MDC

For this, one must replace ${\mathcal{S}}$ with a linear (and not affine) space. Replace constant ${1}$ in (0) by a variable ${x_0}$. If ${x_0=1}$, we are done by previous analysis. If ${x_0 =0}$, we are in a big trouble.

Attempt: construct a dummy NAND instance ${I'}$ such that if we apply reduction to ${I'}$, then any codeword which has ${x_0 =0}$ must have large weight. Then apply reduction to ${I\cup I'}$.

This ${I'}$ instance has ${n^2}$ variables ${y_{ij}}$, and constraints ${y_{ij}=y_i y_j}$. We fix a linear code ${C\subset \mathbf{F}_2^n}$, and impose extra constraints that ${y\in C\otimes C}$, ${diag(y)\in C}$, ${y=y^{\top}}$.

References

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