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 ℓ -wise independent source. That is, the set of vectors from the input vector space are mapped to an ℓ -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 − ℓ -approximation to MAXEkSAT.
Let C ⊆ F 2 n be a linear code such that C ⊥ has distance greater than ℓ + 1 . Then C is an ℓ -wise independent source.
It is sufficient to show that given any k × l matrix M, where k is greater than or equal to l, such that the rank of M is l, for all x ∈ F 2 k , x M 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 x M 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 = x M , 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 ∈ 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.
Recall that BCH2,m,d is an [ n = 2 m , n − 1 − ⌈ d − 2 / 2 ⌉ m , d ] 2 linear code.
Let C ⊥ be BCH2,log n,ℓ+1. Then C is an ℓ -wise independent source of size O ( n ⌊ ℓ / 2 ⌋ ) .
The dimension d of C is just ⌈ ( ℓ + 1 − 2 ) / 2 ⌉ log n + 1 . So d = ⌈ ( ℓ − 1 ) / 2 ⌉ log n + 1 = ⌊ ℓ / 2 ⌋ log n + 1 .
So the cardinality of C considered as a set is just 2 d = O ( n ⌊ ℓ / 2 ⌋ ) , proving the Corollary.
