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




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



About metric2011

metric2011 is a program of Centre Emile Borel, an activity of Institut Henri Poincaré, 11 rue Pierre et Marie Curie, 75005 Paris, France. See
This entry was posted in Workshop lecture and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s