\iffalse


\fi


\documentclass[10pt]{article}
\input{preamble.tex}
\usepackage{amsfonts}
%\usepackage{amsthm}
\usepackage{fullpage}
%\usepackage{epsfig}
\usepackage[margin=1.25in,dvips]{geometry}
%\usepackage{amsthm}
\usepackage{fullpage}

\usepackage{times}
\usepackage{graphicx}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{float}
\usepackage{url}
\usepackage{enumerate}
\usepackage{subfig}
\usepackage[boxed,section]{algorithm}
\usepackage{algpseudocode}
\usepackage{color}
\usepackage[table]{xcolor}

\usepackage{epsfig} % needed for new xfig version
\usepackage{graphics}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsmath}

\usepackage{algorithm}
%\usepackage{algorithmic}
\usepackage{algorithmicx}
\usepackage[fleqn,tbtags]{mathtools}
%\usepackage{amsthm}

\iffalse{
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{assumption}[theorem]{Assumption}
}\fi

\begin{document}

\lecture{13}{March 20, 2013}{Madhu Sudan}{Badih Ghazi}

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

This lecture is about list-decoding folded Reed-Solomon codes. Folded Reed-Solomon codes will be list-decodable codes from a $1 - R - \epsilon$ fraction of errors where $R$ is the rate and $\epsilon >0$. This class of codes was introduced by Guruswami and Rudra \cite{guruswami2006explicit} and was inspired by the work of Parvaresh and Vardy \cite{parvaresh2005correcting}. The particular algorithm that we will describe is due to Guruswami \cite{guruswami2011linear}.

\section{History}

This line of work has an interesting history that we now briefly describe. Fix a prime power $q$ and let $\alpha_1,\dots,\alpha_n \in \mathbb{F}_{q}$. The message will consist of $2$ polynomials $p_1(x), p_2(x) \in \mathbb{F}_{q}[x]$ of degree less than $k$. The codeword will consist of the evaluations of $p_1$ and $p_2$ on the set $\{\alpha_i ~ | ~ i \in [n]\}$. Instead of viewing this code as having length $2n$ over $\mathbb{F}_{q}$, we will view it as having length $n$ over $\mathbb{F}_{q}^{2}$. Note that $\mathbb{F}_{q}^{2}$ is not a finite field. Such codes are usually referred to as ``Interleaved Reed-Solomon Codes''.

\subsection{Coppermisth-Sudan}
Coppermisth and Sudan gave an algorithm for list-decoding interleaved codes but they needed to assume that the error pattern was ``random'' \cite{coppersmith2003reconstructing}. More precisely, the assumption was that some symbols are received uncorrupted whereas other symbols are completely random. The given algorithm recovers from a $1-O((k/n)^{2/3})$ fraction of ``random'' errors.

\subsection{Parvaresh-Vardy}
Instead of letting $p_1(x)$ and $p_2(x)$ be unrelated, Parvaresh and Vardy related them in the following way. Let $\mathbb{F}_{q}^{<k}[x]$ be the ring of all polynomials of degree $<k$ and with coefficients in $\mathbb{F}_{q}$. We define an operator $\Phi:\mathbb{F}_{q}^{<k}[x] \to \mathbb{F}_{q}^{<k}[x]$ and let $p_2(x) = \Phi(p_1(x))$. They were able to show that if the operator $\Phi$ is ``nice'', then there is an algorithm that can recover from a $1-(k/n)^{2/3}$ fraction of errors in the adversarial setting. The drawback of this scheme is that the rate got divided by $2$. In fact, since $p_2(x)$ is determined by $p_1(x)$, $k/n$ is now twice the rate. Thus, this code is list-decodable for a $1 - (2R)^{2/3}$ fraction of errors. This code can be generalized for any constant $c \in \mathbb{N}$ where we can recover from a $1 - (cR)^{c/(c+1)}$ fraction of errors. It looked as if the factor $c$ next to the rate $R$ was inevitable until Guruswami and Rudra came up with the following idea.

\subsection{Guruswami-Rudra}
Guruswami and Rudra \cite{guruswami2006explicit} introduced the following ``nice'' operator $\phi$. We fix a primitive element $\omega$ of $\mathbb{F}_{q}^{*}$ and we let $\phi$ map $p_1(x)$ to $p_1(\omega x)$. Note that the choice of the operator in the Pavaresh-Vardy construction does not change the rate of the code. The first row of the interleaved codeword looks like $p(\omega),p(\omega^2),\dots,p(\omega^{q-1})$ whereas the second row looks like $p(\omega^2),p(\omega^3),\dots,p(\omega^{q})$. All those symbols can be read from $p(\omega)$,\dots,$p(\omega^q)$. Thus, the rate went up from $\frac{1}{2}\frac{k}{n}$ to $\frac{4}{5}\frac{k}{n}$. Thus, this code can recover from a $1 - (\frac{5}{4}R)^{2/3}$ fraction of errors, which is an improvement over the Parvaresh-Vardy codes. The Guruswami-Rudra codes can be further generalized so that we can recover from a $1 - (\frac{(m+s)R}{m})^{\frac{s}{s+1}}$ fraction of errors where $s$ is the number of blocks that we are interleaving and the alphabet is $\mathbb{F}_{q}^{m}$. We will next present a simplified version of the Guruswami-Rudra codes due to Guruswami \cite{guruswami2011linear} that allows us to recover from an $\frac{s}{s+1}(1-\frac{(m+s)}{m}R)$ fraction of errors. Note that this is slightly worse than the performance of the Guruswami-Rudra codes.

\section{Description and analysis of the folded Reed-Solomon codes}
The number of blocks $s$ that we are interleaving is a parameter of the algorithm. In the following description, we will assume for simplicity that $s=2$. Moreover, we let $m=2$ i.e., the code will be over the alphabet $\mathbb{F}_{q}^{2}$.

\subsection{Encoding}
The encoding of the message corresponding to the polynomials $p_1(x), p_2(x) \in \mathbb{F}_{q}^{<k}[x]$ consists of $2$ vectors $(\beta_1,\dots,\beta_n)$ and $(\gamma_1,\dots,\gamma_n)$ where $\beta_i = p_1(\alpha_i)$ and $\gamma_i = p_2(\alpha_i)$ for all $i \in [n]$.

\subsection{List Decoding}
The goal of list-decoding is to find all polynomials $p(x) \in \mathbb{F}_{q}[x]$ of degree less than $k$ s.t.
\begin{equation}\label{le:list_decoding_eqn}
|\{i ~ | ~ \beta_i = p(\alpha_i) \text{ and } \gamma_i = p(\omega \alpha_i)\}| \geq n/3 + (2k)/3
\end{equation}
Note that this is better than unique decoding since $n/3$ appears in the equation as opposed to $n/2$. A priori, it is not clear that the number of polynomials that satisfy Equation (\ref{le:list_decoding_eqn}) is small. We start by finding some ``algebraic explanation'' for the polynomials that satisfy this equation. Namely, we find $Q(x,y,z) = A(x) + B(x)y + C(x)z$ s.t. $Q(x,y,z)$ is not identically equal to $0$ but $Q(\alpha_i,\beta_i,\gamma_i) = 0$ for all $i \in [n]$, $\operatorname{deg}(A) < \frac{n+2k}{3}$, $\operatorname{deg}(B) \le \frac{n-k}{3}$ and $\operatorname{deg}(C) \le \frac{n-k}{3}$. Note that this is a system of linear homogeneous equations.

\begin{claim}
$Q(x,y,z)$ can be found.
\end{claim}

\begin{proof}
This can be done by solving the big linear homogeneous system of equations above.
\end{proof}
We can thus find $A(x),B(x),C(x)$ which determine $Q(x,y,z)$.

\begin{claim}
$Q(x,p_1(x),p_2(x))$ is identically equal to $0$ provided that the number of agreements is at least $\frac{n}{3} + \frac{2k}{3}$.
\end{claim}

\begin{proof}
Define $g(x) = Q(x,p_1(x),p_2(x))$. Since $\operatorname{deg}(g) < \frac{n}{3} + \frac{2k}{3}$ and since $g(\alpha_i) = 0$ for all $i$ s.t. $p_1(\alpha_i) = \beta_i$ and $p_2(\alpha_i) = \gamma_i$, we conclude that $g$ is identically equal to $0$.
\end{proof}

Thus, the set of all $p_1(x), p_2(x) \in \mathbb{F}_{q}^{<k}[x]$ s.t. $A(x) + B(x)p_1(x) + C(x)p_2(x) = 0$ and $p_2(x) = p_1(\omega x)$ includes the polynomials that we are interested in. Note that we can write $p_1(x)$ and $p_2(x)$ as follows
\begin{equation*}
p_1(x) = \displaystyle\sum\limits_{i=0}^{k-1} c_i x^i
\end{equation*}
\begin{equation*}
p_2(x) = \displaystyle\sum\limits_{i=0}^{k-1} \tilde{c}_i x^i
\end{equation*}
where $c_i, \tilde{c}_i \in \mathbb{F}_{q}$ for all $i \in \{0,1,\dots,k-1\}$. We need to find all such $p_1(x)$ and $p_2(x)$ and ensure that there are not too many of them. To do so, we use the following nice idea from the work of Pavaresh and Vardy. We mod out $F_{q}[x]$ by some irreducible polynomial $h(x) \in F_{q}[x]$ in order to get a field. Guruswami and Rudra picked $h(x) = x^{q-1}-\omega$. We will use the following fact.
\begin{fact}
If $\omega$ is a primitive element of $\mathbb{F}_{q}^{*}$, then $x^{q-1}-\omega$ is irreducible over $\mathbb{F}_{q}$.
\end{fact}
Then, $\mathbb{K} = \mathbb{F}_{q}[x] / (x^{q-1}-\omega)$ is a field. Note that in $\mathbb{K}$, we have that $\omega = x^{q-1}$ which implies that $\omega x = x^q$. Thus, we have that $p_2(x) = p_1(\omega x) = p_1(x^q) = (p_1(x))^q$. We need to solve the equation $A(x) + B(x)p_1(x) + C(x)(p_1(x))^{q} = 0$ where $A(x), B(x), C(x) \in \mathbb{K}$ are given and $p_1(x) \in \mathbb{K}$ is the unknown. We can find the set of all solutions $(p_1(x),p_2(x))$ by factoring the polynomial $f(x) = A(x) + B(x)p_1(x) + C(x)(p_1(x))^{q}$ in $\mathbb{F}_{q}[x]$. Since $f(x)$ has degree $q$, the number of solutions is at most $q$. Thus the size of the list is at most $q$. For general values of $s$, this construction yields a list size bound of $q^{s-1}$. We next consider the question of whether we can somewhat reduce the list size.

\section{Reducing the list size}
The Guruswami-Rudra construction and the Guruswami construction both have the property that for sufficiently large values of $s$ and $m$ (that depend on $\epsilon$), the list decoding radius exceeds $1-R-\epsilon$ but the list size bound is $n^{\Omega(\frac{1}{\epsilon})}$ which has a rather poor dependence on the distance parameter $\epsilon$ to the optimal tradeoff. Note that existentially a list size as small as $O(1/\epsilon)$ is possible. In order to reduce the list size, Guruswami \cite{guruswami2011linear} came up with the proposal which was later implemented of Dvir and Lovett \cite{dvir2012subspace}. Since the polynomial $p_1(x)$ comes from an $(s-1)$-dimensional affine subspace, we can restrict the space of all possible messages to those that don't have too many polynomials in any particular low-dimensional subspace. Previously, we were thinking of $p_1(x)$ as an element of $\mathbb{F}_{q}^{k}$. Now we think of $p_1(x)$ as an element of $S \subseteq \mathbb{F}_{q}^{k}$ where $S$ has the following property: For every affine subspace $L \subseteq \mathbb{F}_{q}^{k}$ s.t. $\operatorname{dim}(L) = s-1$, $|L \cap S|$ is ``small'' i.e. $|L \cap S| \le \tau = \operatorname{poly}(1/\epsilon)$. Such as set $S$ is said to be $(s,\tau)$-evasive. Guruswami proved existentially that $|S| \geq q^{(1-o(1))k}$ and Dvir and Lovett later gave an explicit construction.

\section{Linearity of the codes}
Note that the types of codes described above are not linear. Guruswami and Rudra noted that by an ``appropriate composition'' with an appropriate code, we can get the following statement.
\begin{theorem}(\cite{guruswami2006explicit})\\
For all $\epsilon,R>0$, there exists $q,n \in \mathbb{N}$, and $\mathbb{F}_{q}$-linear codes of length $n$ over $\mathbb{F}_{q}$, rate $R$ and that are list-decodable from a $1-R-\epsilon$ fraction of errors, with lists of size $n^{\operatorname{poly}(1/\epsilon)}$.
\end{theorem}

\bibliographystyle{alpha}
\bibliography{Lecture_13.bib}

\end{document}

