\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<k<n$ and $n$ relatively prime 
integers $p_1 < p_2 < \cdots < p_n$ has as its message set,
the set of integers $\Z_K = \{0,\ldots,K-1\}$ where $K = 
\prod_{i=1}^k p_i$ and encodes a message $m \in \Z_K$ as
the $n$-tuple $\langle m (\mod p_1), \ldots, m (\mod p_n) \rangle$.
\begin{enumerate}
\item 
Applying reasoning analogous to the abstract decoding algorithm
used to decode AG codes, show that an efficient solution to 
the following task yields an efficient decoding algorithm for
the CRT code:
\begin{quote}
Given $r_1,\ldots,r_n$ and bounds $L,U$ find $a \in \Z_L$
and $b \in \Z_U$ such that $a \cdot r_i = b (\mod p_i)$ for
every $i \in [n]$.
\end{quote}
How many errors does your algorithm correct? 

For the curious: Show how the above task can be expressed as
an integer programming problem in a {\em constant} (independent
of $n,k,p_i$'s) number of variables.
\item (Hard question) 
Using the fact that the algorithm above has nice
"errors and erasures" correcting behavior, derive an algorithm to 
correct from $(n-k)/2$ errors.
\end{enumerate}

\item {\sf (Johnson bound for large alphabets:)}
Let $B$ be a bipartite graph with $n$ vertices on the left
and $\ell$ vertices on the right with the property that it
has no $K_{m,2}$ (i.e., no induced subgraph that is a 
complete bipartite graph with $m$ vertices on the left 
and $2$ vertices on the right) and every right vertex has
degree at least $t$. Show that if $t^2 > 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}