NumXL: Difference between revisions

Revision as of 13:56, 7 August 2013

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.

Lemma

Let $C \subseteq F_{2}^{n}$ be a linear code such that $C^{⊥}$ has distance greater than $ℓ + 1$ . Then $C$ is an $ℓ$ -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}$ , $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} \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 - ⌈ d - 2 / 2 ⌉ m, d]_{2}$ linear code.

Let $C^{⊥}$ be BCH_{2,log n,ℓ+1}. Then $C$ is an $ℓ$ -wise independent source of size $O (n^{⌊ ℓ / 2 ⌋})$ .

Proof of Corollary

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.

References

Coding Theory notes at University at Buffalo

Coding Theory notes at MIT

@@ Line 1: / Line 1: @@
-year old Osteopath Gordon Pale from St. Catharines, has several pursuits including genealogy, pawn shop and horse racing. Recollects what a striking location it was having gone to Comoé National Park.<br><br>my site: [https://b5b6a2804591849e9557635b349492d48bbc6965.googledrive.com/host/0B0ArFwQ_4S04VVpodHdkb25kN0k/Pawn-Shop-Phoenix Extra resources]
+A certain family of [[BCH code]]s have a particularly useful property, which is that
+treated as [[linear operator]]s, their [[dual basis|dual operators]] turns their input into an <math>\ell</math>-wise [[pairwise independence|independent source]].  That is, the set of vectors from the input [[vector space]] are mapped to an <math>\ell</math>-wise independent source.  The proof of this fact below as the following Lemma and Corollary is useful in derandomizing the algorithm for a <math>1-2^{-\ell}</math>-approximation to [[MAXEkSAT]].
+==Lemma==
+Let <math>C\subseteq F_2^n</math> be a linear code such that <math>C^\perp </math> has distance greater than <math> \ell +1</math>.  Then <math>C</math> is an <math>\ell</math>-wise independent source.
+==Proof of Lemma==
+It is sufficient to show that given any <math>k \times l</math> matrix ''M'', where ''k'' is greater than or equal to ''l'', such that the rank of ''M'' is ''l'', for all <math>x\in F_2^k</math>, <math>xM</math> takes every value in <math>F_2^l</math> the same number of times.
+Since ''M'' has rank ''l'', we can write ''M'' as two matrices of the same size, <math>M_1</math> and <math>M_2</math>, where <math>M_1</math> has rank equal to ''l''.  This means that <math>xM</math> can be rewritten as <math>x_1M_1 + x_2M_2</math> for some <math>x_1</math> and <math>x_2</math>.
+If we consider ''M'' written with respect to a basis where the first ''l'' rows are the identity matrix, then <math>x_1</math> has zeros wherever <math>M_2</math> has nonzero rows, and <math>x_2</math> has zeros wherever <math>M_1</math> has nonzero rows.
+Now any value ''y'', where <math>y=xM</math>, can be written as <math>x_1M_1+x_2M_2</math> for some vectors <math>x_1, x_2</math>.
+We can rewrite this as:
+<math>x_1M_1 = y - x_2M_2</math>
+Fixing the value of the last <math>k-l</math> coordinates of
+<math>x_2\in F_2^k</math> (note that there are exactly <math>2^{k-l}</math>
+such choices), we can rewrite this equation again as:
+<math>x_1M_1 = b</math> for some ''b''.
+Since <math>M_1</math> has rank equal to ''l'', there
+is exactly one solution <math>x_1</math>, so the total number of solutions is exactly <math>2^{k-l}</math>, proving the lemma.
+==Corollary==
+Recall that BCH<sub>2,''m'',''d''</sub> is an <math> [n=2^m, n-1 -\lceil {d-2}/2\rceil m, d]_2</math> linear code.
+Let <math>C^\perp</math> be BCH<sub>2,log&nbsp;''n'',''ℓ''+1</sub>.  Then <math>C</math> is an <math>\ell</math>-wise independent source of size <math>O(n^{\lfloor \ell/2 \rfloor})</math>.
+==Proof of Corollary==
+The dimension ''d'' of ''C'' is just <math>\lceil{(\ell +1 -2)/{2}}\rceil \log n +1 </math>.  So <math>d = \lceil {(\ell -1)}/2\rceil \log n +1 = \lfloor \ell/2 \rfloor \log n +1</math>.
+So the cardinality of <math>C</math> considered as a set is just
+<math> 2^{d}=O(n^{\lfloor \ell/2 \rfloor})</math>, proving the Corollary.
+== References ==
+[http://www.cse.buffalo.edu/~atri/courses/coding-theory/ Coding Theory notes at University at Buffalo]
+[http://people.csail.mit.edu/madhu/FT01/course.html/ Coding Theory notes at MIT]
+[[Category:Article proofs]]

NumXL: Difference between revisions

Revision as of 13:56, 7 August 2013

Contents

Lemma

Proof of Lemma

Corollary

Proof of Corollary

References

Navigation menu

NumXL: Difference between revisions

Revision as of 13:56, 7 August 2013

Lemma

Proof of Lemma

Corollary

Proof of Corollary

References

Navigation menu

Search