Add list decoding

1 files changed, 21 insertions, 0 deletions

diff --git a/ps4/main.tex b/ps4/main.tex
index ecda8e0..009219d 100644
--- a/ps4/main.tex
+++ b/ps4/main.tex
@@ -143,6 +143,27 @@ code, $2^{2m}$, is $O(\frac{n^2}{\eps^2})$ as requested.
 Since $m = O(\log \frac{n}{\eps})$ and $m(d+1) = n$, it is clear that the code
 is fully explicit.
 
+\paragraph{} To get list-decoding, we need a different setting of $m$. We know
+that the Hadamard code can be $\frac{1}{2}-\frac{\eps}{2}$ list-decoded for any
+$\eps$ with list length $l_2 = \Theta(\frac{1}{\eps^2})$. If we set $m$ such
+that:
+\begin{displaymath}
+2l_2\sqrt{\frac{n}{m2^m}} = \eps
+\end{displaymath}
+i.e $\frac{n}{m2^m} = \Theta(\eps^6)$,  then applying \textbf{2.} the
+concatenated code will have distance
+$(1-\eps)(\frac{1}{2}-\frac{\eps}{2}) \geq (\frac{1}{2}
+-\eps)$.  The resulting list length will be $\sqrt{\frac{m2^m}{d}}l_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
+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
+= \Theta(\frac{1}{\eps^2})$ times, so the overall resulting running time is
+still polynomial.
+
 \section*{Problem 5.6}
 
 \paragraph{1.} I follow the hint by allowing the bivariate polynomial $Q$ in