NumXL

A certain family of BCH codes have a particularly useful property, which is that treated as linear operators, their dual operators turns their input into an $\ell$-wise independent source. That is, the set of vectors from the input vector space are mapped to an $\ell$-wise independent source. The proof of this fact below as the following Lemma and Corollary is useful in derandomizing the algorithm for a $1-2^{-\ell }$-approximation to MAXEkSAT.

Lemma

Let $C\subseteq F_2^n$ be a linear code such that $C^{\perp }$ has distance greater than $\ell +1$. Then $C$ is an $\ell$-wise independent source.

Proof of Lemma

It is sufficient to show that given any $k\times l$ matrix M, where k is greater than or equal to l, such that the rank of M is l, for all $x\in F_2^k$, $xM$ takes every value in $F_2^l$ the same number of times.

Since M has rank l, we can write M as two matrices of the same size, $M_1$ and $M_2$, where $M_1$ has rank equal to l. This means that $xM$ can be rewritten as $x_1{M}_1+x_2{M}_2$ for some $x_1$ and $x_2$.

If we consider M written with respect to a basis where the first l rows are the identity matrix, then $x_1$ has zeros wherever $M_2$ has nonzero rows, and $x_2$ has zeros wherever $M_1$ has nonzero rows.

Now any value y, where $y=xM$, can be written as $x_1{M}_1+x_2{M}_2$ for some vectors $x_1,x_2$.

We can rewrite this as:

$x_1{M}_1=y-x_2{M}_2$

Fixing the value of the last $k-l$ coordinates of $x_2\in F_2^k$ (note that there are exactly $2^{k-l}$ such choices), we can rewrite this equation again as:

$x_1{M}_1=b$ for some b.

Since $M_1$ has rank equal to l, there is exactly one solution $x_1$, so the total number of solutions is exactly $2^{k-l}$, proving the lemma.

Corollary

Recall that BCH_2,m,d is an $[n=2^m,n-1-\lceil d-2/2\rceil m,d{]}_2$ linear code.

Let $C^{\perp }$ be BCH_{2,log n,ℓ+1}. Then $C$ is an $\ell$-wise independent source of size $O(n^{\lfloor \ell /2\rfloor })$.

Proof of Corollary

The dimension d of C is just $\lceil (\ell +1-2)/2\rceil \log n+1$. So $d=\lceil (\ell -1)/2\rceil \log n+1=\lfloor \ell /2\rfloor \log n+1$.

So the cardinality of $C$ considered as a set is just $2^d=O(n^{\lfloor \ell /2\rfloor })$, proving the Corollary.

References

Coding Theory notes at University at Buffalo

Coding Theory notes at MIT