diff options
| -rw-r--r-- | ps4/main.tex | 21 |
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 |