[ps4] last question

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}