\documentclass[11pt]{article}
\usepackage{fullpage}
\usepackage{amsfonts}
\newcommand{\np}{\mathop{\rm NP}}
\newcommand{\binom}[2]{{#1 \choose #2}}
\newcommand{\Z}{{\mathbb Z}}
\newcommand{\F}{{\mathbb F}}
\newcommand{\vol}{\mathop{\rm Vol}}
\newcommand{\conp}{\mathop{\rm co-NP}}
\newcommand{\atisp}{\mathop{\rm ATISP}}
\newcommand{\mod}{\mathop{\rm mod}}
\newcommand{\calc}{{\cal C}}
\renewcommand{\vec}[1]{{\mathbf #1}}
%\input{dansmacs}
\begin{document}
\noindent {\large Essential Coding Theory \hfill
Madhu Sudan\\[-.1in]
6.896 \hfill \mbox{}\\[-.1in]
Due: Wednesday, December 4, 2002\hfill \mbox{}\\[.4in]}
{\LARGE \centering Problem Set 4 \\[.4in] \par}
\noindent {\bf Instructions:} See PS1.
\begin{enumerate}
%\item {\sf Peterson's Key Equation:}
\item {\sf (Decoding the CRT code:)}
Recall that the Chinese Remainder Theorem based code (CRT
codes) with integer parameters $0 mn$, then $\ell \leq
n(t-m)$.
Assuming the above, show that
an $[n,k,d+1]_q$ code $C$ is also $(e.\ell)$-error-correcting
for $e = n - \sqrt{n(n-d)}$ and $\ell = O(n)$.
(recall defn. from Lecture 13. )
%\item {\sf RM list-decoding}
\item {\sf (Decoding Tanner codes:)}
Recall the codes described in Lecture 16, Section 6 introduced by
Tanner.
These are codes obtained
by combining a $(c,d)$-regular $(\delta,\gamma)$-bipartite expander
with a constant sized error correcting code $C'$ of minimum
distance $\Delta$.
Consider the following decoding algorithm
for this code, which proceeds in stages, with the $i$th stage
as follows:
\begin{itemize}
\item The iteration starts with a current assignment to left
vertices.
\item If each right vertex sees a codeword of $C'$, then output
the current assignment and stop.
\item Else, in parallel each right vertex does the following:
If the assignment to its neighbors is at distance at most
$\epsilon \Delta$ from some codeword, then send a FLIP message
to every left neighbor that is inconsistent with the nearest
codeword of $C'$.
\item In parallel, every left vertex that receives at least
one FLIP message from its neighbors, flips its current assignment.
\end{itemize}
Show that the above algorithm corrects a constant fraction of
errors (provided $\gamma>0$, and $\epsilon < O(1/c)$ and
$\Delta$ is sufficiently large).
Also give sufficient conditions for the rate of this code
to be positive.
(Email madhu@mit.edu for hints!)
\item {\sf (Rate vs. list-decodability:)}
\begin{enumerate}
\item Let $\calc$ be an infinite family of codes of rate $R$
such that every code of block length $n$ in $\calc$ is
$(\tau n, n)$ list-decodable. Show that $R \leq 1 - H(\tau)$.
\item For any $R, \tau$ such that $R < 1 - H(\tau)$, prove that
there exists an infinite family of codes $\calc $ of rate
$R < 1 - H(\tau)$ is $(\tau n, O(n))$-list decodable.
\end{enumerate}
\end{enumerate}
\end{document}