diff options
Diffstat (limited to 'ps4/main.tex')
| -rw-r--r-- | ps4/main.tex | 42 |
1 files changed, 34 insertions, 8 deletions
diff --git a/ps4/main.tex b/ps4/main.tex index 009219d..3b13700 100644 --- a/ps4/main.tex +++ b/ps4/main.tex @@ -87,13 +87,13 @@ This proves that the minimum distance of $\Enc$ is at least $\delta_1\delta_2$. the homework was due!)} Let us consider a received word $r$, and a message $m$ such that $d(\Enc(m), r)\leq (1-\eps_1l_2)\delta_2$. We can view $r$ as the concatenation of $n_1$ blocks, each of size $n_2$. Denoting by $r_i$ the $i$th -block, I first note that the fraction of $i$s such that $d(r_i, -\Enc_2(\Enc_1(m)_i)$ is at most $(1-\eps_1l_2)$. Otherwise, by summing over $i$ +block, I first note that the fraction of indicdes $i$ such that $d(r_i, +\Enc_2(\Enc_1(m)_i))> \delta_2$ is at most $(1-\eps_1l_2)$. Otherwise, by summing over $i$ we would have $d(Enc(m), r)> (1-\eps_1l_2)\delta_2$, a contradiction. Hence, by $l_2$ list-decoding each of the blocks $r_i$, we obtain $n_1$ lists -of $l_2$ characters from $\Sigma_1$, such the $i$s such that the $i$th list -does not contain $\Enc_1(m)_i$ are a fraction at most $(1-\eps_1l_2)$. +of $l_2$ characters from $\Sigma_1$, such the indices $i$ such that the $i$th +list does not contain $\Enc_1(m)_i$ are a fraction at most $(1-\eps_1l_2)$. I now construct $l_2$ words $c_1,\dots, c_{l_2}$ such that $c_j$ is obtained by taking the $j$th character in each of the $n_1$ lists of length $l_2$ obtained @@ -101,7 +101,7 @@ by $l_2$ list-decoding in the previous paragraph. I claim that one of those words $c_j$ is such that $d(c_j, Enc_1(m))\leq 1-\eps_1$. Otherwise, by summing over $j$, and denoting by $f$ the fraction of -$i$s such that the $i$th list does not contain $\Enc_1(m)_i$: +indices $i$ such that the $i$th list does not contain $\Enc_1(m)_i$: \begin{align*} (1-\eps_1)l_2&< \sum_{j=1}^{l_2} d(c_j, Enc_1(m)) = \frac{1}{n_1}\sum_{i=1}^{n_1}\sum_{j=1}^{l_2} \left[(c_j)_i\neq @@ -112,7 +112,7 @@ $i$s such that the $i$th list does not contain $\Enc_1(m)_i$: where the second equality was obtained by splitting the sum over $i$ depending on whether or not $\Enc_1(m)_i$ belongs to the $i$th list, and the last inequality was obtained by using the bound on $f$ found in the first paragraph -of this answer. Looking at the two extremal terms of the above computation, we +of this answer. Looking at the two extremal terms in the above computation, we see a contradiction. Hence, one of the $c_j$ is such that $d(c_j, Enc_1(m))\leq @@ -157,7 +157,7 @@ $(1-\eps)(\frac{1}{2}-\frac{\eps}{2}) \geq (\frac{1}{2} =\Theta(\frac{1}{\eps^5})$. The inner Hadamard code as $2^m = \Theta(\frac{n}{\eps^6})$ code-words, so the -list-decoding can be done in polynomial time by brute force testing all +list-decoding can be done in polynomial time by brute-force testing all code-words. Finally, since $m = \Theta(\log \frac{n}{\eps^6})$, The outer RS code can be list-decoded in polynomial time using the algorithm seen in class. Note that by \textbf{2.} we only need to apply this algorithm $l_2 @@ -220,6 +220,32 @@ distance $\frac{1}{4}+\eps$, we are guaranteed that the list $L$ of length $l$ returned by the decoder contains one of the two secrets. By assumption, the decoding takes polynomial time. -\paragraph{2.} +\paragraph{2.} First, we verify that the code-words in the concatenated code of +Problem 5.2.3 have sufficient agreement. Denoting by $a(\cdot,\cdot)$ the +agreement between two words, let us consider two different messages $m_1$ and +$m_2$ of the code of Problem 5.2.3: +\begin{displaymath} + a\big(\Enc(m_1), \Enc(m_2)\big) = 1- d\big(\Enc(m_1), \Enc(m_2)\big) + = 1 - d\big(\Enc_1(m_1), \Enc_2(m_2)\big)\frac{1}{2} +\end{displaymath} +where the last equality used the following reasoning (this is basically the +same thing as \textbf{1.} plus using that Hadamard codes have constant +distance): +\begin{itemize} + \item on the positions where $\Enc_1(m_1)$ and $\Enc_1(m_2)$ coincide, then + the resulting blocks after applying $\Enc_2$ will be identical and do + not contribute anything to the $d\big(\Enc(m_1), \Enc(m_2)\big)$. + \item on the positions where $\Enc_1(m_1)$ and $\Enc_1(m_2)$ differ, the + resulting blocks after applying $\Enc_2$ will differ on exactly half + the positions, because for the Hadamard code, the distance between any + two different codewords is $\frac{1}{2}$. +\end{itemize} +Since the distance is at most 1, we get that the agreement is at least +$\frac{1}{2}$ which is a sufficient condition given \textbf{1.}. +Hence, we can directly apply the last part of Problem 5.2.3 with $\eps += \frac{1}{4}-\eps'$ for some $\eps'< \frac{1}{4}$ and obtain +a $(\frac{1}{4}+\eps', \mathrm{poly}(\frac{1}{1/4-\eps'}))$ list decodable +code. The number of questions (blocklength) will be $\mathrm{poly}(n)$ for +$\eps'$ a small enough constant. \end{document} |