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.
