\documentclass[10pt]{article}
\usepackage{amsfonts}
\newtheorem{define}{Definition}

%\newcommand{\Z}{{\bf Z}}
\usepackage{epsfig}

\oddsidemargin=0.15in
\evensidemargin=0.15in
\topmargin=-.5in
\textheight=9in
\textwidth=6.25in

\begin{document}
\input{preamble.tex}

\lecture{8}{October 4, 2004}{Madhu Sudan}{Anindya C. Patthak}

%%%% body goes in here %%%%

\section{Overview}
In this lecture we will cover List Decoding of Reed-Solomon Codes.
\section{List Decoding of Reed-Solomon Codes: Combinatorial
Perspective} \label{sec:ListDecodingCombinatorial}
 In the last lecture we have seen the combinatorial version of
 list decoding. Recall that
we are given a code of distance $d$ and we would like to correct
more than $d/2$ errors. We argued that unique decoding is not
possible. Therefore we decided on outputting a small list of
codewords that has good agreement with the received word. We
established the following combinatorial version of list decoding
that ensured existence of a polynomial size list provided the
agreement is suitably large.
\begin{theorem}
\label{thm:JohnsonBound}(Combinatorial Version) Let $C$ be an
$(n,k,d)$ error\footnote{The bound on list size does not depend on
the dimension $k$.} correcting code over an alphabet $\Sigma$ of
size $q$. Then given any ball $B(x,r)$, where $x\in \Sigma^n$ and
$r=n-\sqrt{(n-d)n}$, the set $C\cap B(x,r)$ has size at most
$\poly(n)$, more specifically $n^2$.
\end{theorem}
\begin{definition}
\label{defn:elCorrectingCode} Given an $[n,k,d]_q$ code $C$ over
an alphabet $\Sigma$, we say that $C$ is $(e,\ell)$-list decodable
code, if for every $x\in \Sigma^n$, $B(x,e)\cap C$ has size at
most $\ell$.
\end{definition}

The following corollary is then immediate from Theorem
\ref{thm:JohnsonBound}.
\begin{corollary}
\label{cor:JohnsonBoundForRS} ({\bf List Decoding of Reed-Solomon
Codes}:Combinatorial Version) An $[n,k,n-k+1]_q$ $\rs$ code is
$(n-\sqrt{n(k-1)},n^2)$-list decodable.
\end{corollary}
\section{List Decoding of Reed-Solomon Codes: Algorithmic
Perspective} \label{sec:ListDecodingAlgorithmic} The algorithmic
challenge of list decoding is the following:
\begin{center}
{\em Given an $(e,\ell)$-list decodable code $C$ and any received
word $y=\langle y_1,\cdots,y_n\rangle$, output the set $B(y,e)\cap
C$.}
\\
\end{center}
 For an easier exposition, we give the following definition.
\begin{definition}
\label{defn:agreement} Given $x,y \in \F_q^n$, we define the
agreement between $x$ and $y$ to be
\[ \mbox{agreement}(x,y)\stackrel{def}{=}|\{i|x_i = y_i\}|. \]
\end{definition}
With this definition, we reformulate our list-decoding task the
following way:
\begin{center}
{\em Given any $(e,\ell)$-list decodable code $C$ and a received
word $y=\langle y_1,\cdots,y_n\rangle$, output the set $\{x\in C\;
|\; \mbox{ agreement}(x,y)\geq t\}$, where we set $t=n-e$.}
\end{center}
We now describe an algorithm to list-decode $\rs$ codes from
$(k+1)\sqrt{n}+1$ agreements. With some parameter optimization,
the same algorithm can be used to list-decode $\rs$ codes from
agreements as low as $2\sqrt{kn}+1$. It is possible to improve our
result to correct more errors. There is an algorithm due to
Guruswami and Sudan that can list-decode $\rs$ codes from
agreement as small as $\sqrt{kn}+1$. However, that requires more
sophisticated arguments and therefore we skip.
 \subsection{Problem Formulation}
 \label{sec:Intuition}
 We quickly recall the problem we are considering.
 \begin{tabbing}
 \= \hspace*{0.2in}\= \textsc{Problem}: {\bf List Decoding of Reed-Solomon codes}
     \\
\>    \> \textsc{Input}: $\F, n, k, t$;
     $\alpha_1,\cdots,\alpha_n \in \F$, a received vector
     $\langle{y_1,\cdots,y_n\rangle}\in \F^n$. \\
  \> \>  \textsc{Goal}: Find all polynomials $p$ of degree $<k$ s.t.\
    $p(\alpha_i)=y_i$ for at least $t$ values of $i$.
 \end{tabbing}
 As mentioned earlier our goal today is to find an algorithm for
 $t> (k+1)\sqrt{n}$.
 \par Recall that in Welch-Berlekamp Decoder we
 carry out the following steps:
 \vspace{0.2in} \\
 \hspace{0.2in} \textsc{Welch-Berlekamp Decoder}
 \begin{tabbing}
\= 1. \= Find polynomials $(N,E)$ s.t.\ $N(\alpha_i)/E(\alpha_i)=
y_i$ holds for all $i\in [n]$ provided $E(\alpha_i)\neq 0$ \\
\> 2. \> Output $N(x)/E(x)$
 \end{tabbing}
%We have already seen that if the error is not too large then this
%works.
Alternatively we may think of finding a rational function
``to explain'' the data. We will make this idea precise soon.
Recall that univariate rational functions are functions that are
fraction of two univariate polynomials. They have a form
$f(x)/g(x)$, where $f(x)$ and $g(x)$ are univariate polynomials.
They also need to satisfy the requirement that whenever $g(x)=0$
implies $f(x)=0$. In another words the zero set of polynomial
$g(x)$ is a subset of the zero set of polynomial $f(x)$. Note if
$f(x)$ and $g(x)$ are given explicitly, then it is necessary that
$g(x)$ divides $f(x)$ and this does not give more power than
univariate polynomials. However, the power comes if we do not know
$f(x)$ and $g(x)$ explicitly, but given any $x$, we can compute
$f(x)$ and $g(x)$. Let $r(x)=f(x)/g(x)$ be a rational function.
Suppose $\alpha$ is in the zero set of $g(x)$. Then we know
$g(\alpha)=f(\alpha)=0$. How should we define $r(\alpha)$? A good
idea is to allow $r(\alpha)$ to take any possible value. This is
explained in the Figure~\ref{fig:rationalfunction}.

\fig{fig:rationalfunction}{2.9in}{Interpretation of data through
rational function}{rationalfnc.eps}

 Therefore, given a set of $\{(\alpha_i,y_i)\}_{i\in [n]}$, we
 relax the Welch-Berlekamp-type interpolation problem as follows:
\begin{itemize}
\item (\textsc{Welch-Berlekamp}-type Goal): Find a {\it
polynomial} $p(x)$ such that  $p(\alpha_i)$ {\em equals} $y_i$
{\it for many $i$}
 \item (Reformulation): Find a {\it rational function} $r(x)$ which {\em
 explains} $y_i$ for all $\alpha_i$
\end{itemize}

Thus we replace the claim in Welch-Berlekamp by the following
claim.
\begin{claim}
\label{clm:Welch-Berlekampclm}(Welch-Berlekamp) If $\exists p$ of
degree $<k$ agreeing $\frac{n+k}{2}$ values of $y_i$ then a pair
of polynomials $(N,E)$ exists with $\mbox{deg}(N)\leq
\frac{n+k}{2}$ and $\mbox{deg}(E)\leq \frac{n-k}{2}$ such that
$N(\alpha_i)=E(\alpha_i)p(\alpha_i)$ holds for all $i$.
\end{claim}
\begin{claim}
\label{clm:relaxedWelch-Berlekampclm} (A slight relaxation)  A pair of
polynomials $(N,E)$ exists with $\mbox{deg}(N)\leq \frac{n+k}{2}$
and $\mbox{deg}(E)\leq \frac{n-k}{2}$ such that
$\frac{N}{E}(\alpha_i)= y_i$ holds whenever\footnote{Note thus we
are essentially looking for a rational function in $x$.}
$E(\alpha_i)\neq 0$.
\end{claim}

\begin{proof-sketch}
We solve the linear system $N(\alpha_i)=y_i E(\alpha_i)$ for
$i=1,\cdots, n$. This is a homogenous linear system and therefore
always has a solution. Note $(N,E)\equiv (0,0)$ is a trivial
solution. We will prove that the the system has more than one
solution and thus a non-trivial solution exists. The system can be
reformulated as a matrix-vector equation i.e., $A\cdot
X={\boldmath 0}$ where $A$ is the co-efficient matrix and $X$ is
the unknown vector. Note that the rank of matrix $A$, say $r$, can
be at most $n$. However the number of unknowns is $(n-k)/2+1
+(n+k)/2+1 = n+2$. This system has $|\F|^{n+2-r}$ number of
solutions including the trivial one. Since $r\leq n$, thus there
exists a non-trivial solution.
\end{proof-sketch}



\subsection{Nice Algebraic Interpretations of Data}
\label{subsec:AlgebraicExplaination}
 Earlier we have argued that univariate rational functions are
 generalizations of univariate polynomial functions. It turns out
 that there are even richer class of functions that fits our purpose
  better. Given a set of pairs $\{(\alpha_i,y_i)\}_{i\in [n]}$ we would fit
  them in an algebraic curve in the plane, that is, we would
  construct a bi-variate polynomial $Q(x,y)$ s.t.\
  $Q(\alpha_i,y_i)=0$ for all $i \in [n]$. We make the following
  claim.
  \begin{claim}
  \label{clm:bivariateInterpolation} (Bi-variate Interpolation
  Claim) For every set of pairs $\{(\alpha_i,y_i)\}$ of size $n$,
  there exists a bivariate polynomial $Q(x,y)$ with $\mbox{deg}_x
  (Q ), \mbox{deg}_y(Q)\leq \sqrt{n}$ such that
  \[ Q(\alpha_i,y_i) =0 \mbox{ for all $i\in [n]$ and } Q(x,y)\neq
  0\]
 \end{claim}
\begin{proof-sketch}
   We will set up a linear system with the coefficients of $Q(x,y)$ being unknowns. Note
   from the degree bound, the number of unknown variables is
   $(\sqrt{n}+1)^2$. However the number of constraints is $n$.
   This is an under-constrained system. Therefore the system has
    more than one solution including the trivial one (i.e., identically zero polynomial).
    Thus non-trivial solutions exists.
\end{proof-sketch}
Consider the algebraic curve in Figure~\ref{fig:algebraiccurve}.
An inspection reveals that the curve is given by the equation
$Q(x,y)=(x^4-y^4-x^2+y^2)$.  Note however that there are many
points which fits nicely on simpler curves $(x+y)$, $x-y)$ and
$(x^2+y^2-1)$. Thus to solve the list decoding problems, we can
think of getting an algebraic curves that fits the data nicely.
Then we can hope that the curve may be factored into several
factors and each factor will have good agreement with the data. We
now show that {\em this intuition works}.
 \fig{fig:algebraiccurve}{1.6in}{An algebraic curve that fits many points}{circle.eps}

\subsection{List Decoding of Reed-Solomon Codes}
We  describe the list decoding algorithm.
\newpage
\begin{tabbing}
 \=\hspace*{0.2in} \= \textsc{List Decoding of $\rs$ code} \\
 \> \> \textsc{Input}: $\{(\alpha_i,y_i)\}_{i\in [n]},
 t> (k+1)\sqrt{n}$ \\
 \> \> \textsc{Output}: A list of univariate polynomials
 $p_j$ of degree $\leq k$ such that $p_j(\alpha_i)=y_i$ for at least $t$ \\
 \> \> \hspace*{0.4in} values of  $i$
 \end{tabbing}
 \begin{tabbing}
\= 1. \= Find $Q(x,y)\neq 0$ where
$\mbox{deg}_x(Q),\mbox{deg}_y(Q) \leq \sqrt{n}$ such that
$Q(\alpha_i,y_i)=0$ for all $i$ \\
\> 2. \> Factor $Q(x,y)$ into irreducible polynomials i.e., let
$Q(x,y)=Q_1(x,y)\cdots Q_s(x,y)$ \\
\> 3. \> Output all polynomials $p_1,\cdots p_j$ of degree
$\leq k$ if $(y-p_j(x))\equiv Q_j(x,y)$ and \\
\> \>  $p_j(\alpha_i)=y_i$ for at least $t$ values of $i$
 \end{tabbing}

\begin{claim}
\label{clm:AnalysisOfListDecoder} Algorithm \textsc{List Decoding
of $\rs$ code} runs in poly time and outputs all polynomial $p(x)$
such that $p(\alpha_i)=y_i$ for at least $t$ values of $i$.
\end{claim}
\begin{proof-sketch}
 Step 1 and 3 can clearly be done in polynomial time. Moreover there
 are efficient algorithms to solve the multivariate polynomial factorization
 problem over finite fields (in fact over almost all fields).
Deterministic versions of these algorithms takes
 $poly(\log |\F|,n)$ steps over most fields and $poly(|\F|,n)$ steps
 over few fields\footnote{For example, over a large prime field $\F_p$}.
 However efficient randomized versions are known that runs in
 $poly(\log |\F|,n)$ time for all fields. This ensures that the algorithm is
 efficient i.e., runs in polynomial time.
  \par By Claim~\ref{clm:bivariateInterpolation} we know step 1
 always finds a non-trivial $Q$. Therefore all that remains to show
 is the following: If $p$ has degree $\leq k$ and satisfies
 $p(\alpha_i)=y_i$ for at least $t$ values of $i$ and if $Q(x,y)$
 is an output of step 1, then $(y-p(x))| Q(x,y)$ provided $t>(k+1)\sqrt{n}+1$.
 Assume $p(x)$ is such a polynomial.
 \par How could one hope to prove such divisibility results? In
 general this may be addressed using age-old Bezout's theorem.
 \begin{theorem}
 \label{thm:BezoutTheorem}(Bezout's Theorem in the plane) Let
 $Q_1(x,y)$ and $Q_2(x,y)$ be bivariate polynomials of degree at most
 $D_1$ and $D_2$, respectively  over a field  $F$. If $Q_1(x,y)$
 and $Q_2(x,y)$ have more than $D_1\cdot D_2$ common zeros, then
 they share a non-trivial factor.
 \end{theorem}
 Thus if one of the polynomials is irreducible, then this
 gives a divisibility criteria. It turns out that we can argue
 even simpler. We recall the following innocent lemma.
 \begin{lemma}
 \label{lem:RemainderTheorem}
 (Remainder Theorem) Let $g(y)$ be an univariate polynomial over a field $F$. Then for
 any $\gamma \in \F$, $(y-\gamma) | g(y)$ {\it if and only if}
 $g(\gamma)=0$.
 \end{lemma}
 We mention that the above theorem holds over UFD (Unique
 Factorization Domain). We also mention that $\F[x],\F[x_1,\cdots,x_n]$
 i.e., the ring of univariate and multivariate polynomials over a
 field, are in fact UFD. We will apply the above lemma over
 $\F[x]$.
 \par Recall  we want to show that $(y-p(x))|Q(x,y)$.
 By Lemma~\ref{lem:RemainderTheorem}, it is therefore enough to
 show that $Q(x,p(x))$ is identically zero polynomial. Define
 \[h(x)\stackrel{def}{=} Q(x,p(x)).\]
 The following claim can easily be verified by replacing $y$ by
 $h(x)$.
 \begin{claim}
 \label{clm:hsdegreebound} $\mbox{deg}(h(x)) \leq (1+k) \sqrt{n}$.
 \end{claim}
 By hypothesis we have that $p(\alpha_i)=y_i $ for at least $t$
 values of $i$. Note whenever it holds that $p(\alpha_i)=y_i$,
 we have $h(\alpha_i)=Q(\alpha_i,p(\alpha_i))=Q(\alpha_i,y_i)=0$.
 This implies the following claim.
\begin{claim}
\label{clm:hhasmanyzeros} $h(x)$ has at least $t$ zeros.
\end{claim}
Since a univariate polynomial of degree $d$ can have at most $d$
zeros, from Claims~\ref{clm:hsdegreebound}
 and~\ref{clm:hhasmanyzeros} and the fact that $t> (1+k)\sqrt{n}$ we conclude
 that $h(x)$ must be identically zero polynomial. This concludes the
 analysis.
\end{proof-sketch}

\begin{remark}
\label{rem:numberofsolution}
    Note that the $\mbox{deg}_y(Q)\leq \sqrt{n}$ and therefore it
    can have at most $\sqrt{n}$ factors of the form $(y-p(x))$.
    However this does not improve upon the combinatorial version
    of the list decoding.  The agreement assumed here is much larger than
    the one assumed in the combinatorial version.
\end{remark}

\par We now modify  the interpolation lemma slightly. We now try
 to find a bivariate poly $Q(x,y)$ with $\mbox{deg}_x(Q) \leq
\sqrt{kn} $ and $\mbox{deg}_y(Q) \leq \sqrt{n/k}$. With this
setting the same algorithm can be used to recover codewords from
agreement $t>2\sqrt{kn}$ (can be proved in an analogous fashion).
\begin{theorem}
\label{thm:ImprovedRSListDecoder}  Interpolating with a bivariate
polynomial $Q(x,y)$ with $\mbox{deg}_x(Q)\leq \sqrt{nk}$ and
$\mbox{deg}_y(Q) \leq \sqrt{n/k}$, the algorithm \textsc{List
Decoding of RS code} solves the $\rs$ list decoding problem with
agreements $>2\sqrt{kn}$ in polynomial time.
\end{theorem}

({\bf Notes})
 \begin{enumerate}
 \item As mentioned previously the best
known list decoding algorithm can correct from agreements as low
as $\sqrt{kn}$. Moreover the algorithm does not necessarily
require that all $\alpha_i$'s are distinct. Though it assumes a
bound on the number that a distinct $\alpha_i$ can appear. We
leave the details.

\item Can we do better? A recent result of Guruswami and Rudra
suggest that in order to improve the algorithm we have to exploit
the fact that many $\alpha_i$'s are distinct.
 \item  At this moment all the combinatorial results involving
 Reed-Solomon codes have their algorithmic counterparts.
 We mention that Guruswami and Vardy have recently shown that
 the Maximum-Likelihood Decoding of Reed-Solomon Code is ${\rm
 NP}$-${\rm complete}$.

\end{enumerate}

\end{document}