\documentclass[11pt]{article}
\usepackage{latexsym}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{hyperref}
\newcommand{\handout}[5]{
\noindent
\begin{center}
\framebox{
\vbox{
\hbox to 5.78in { {\bf Computational Complexity II} \hfill Course Instructor: #2 }
\vspace{4mm}
\hbox to 5.78in { {\Large \hfill #5 \hfill} }
\vspace{2mm}
\hbox to 5.78in { {\em #3 \hfill #4} }
}
}
\end{center}
\vspace*{4mm}
}
\newcommand{\lecture}[4]{\handout{#1}{#2}{Lecturer: #3}{Scribe:
#4}{Expander Codes}}
\newtheorem{theorem}{Theorem}
\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}
%my custom commands
\newcommand{\norm}[1]{\left\Vert #1 \right\Vert}
\newcommand{\ltwo}[1]{\left\Vert #1 \right\Vert_2}
\newcommand{\lone}[1]{\left| #1 \right|_1}
\newcommand{\linf}[1]{\left| #1 \right|_{\infty}}
\newcommand{\innerp}[1]{\langle #1 \rangle}
\newcommand{\blah}{x\perp u,\norm{x}=1}
\newtheorem{subclaim}[theorem]{Subclaim}
\newcommand{\z}{\textcircled{z}}
\newcommand{\parn}[1]{\left( #1 \right)}
\newcommand{\ceil}[1]{\lceil #1 \rceil}
\newcommand{\floor}[1]{\lfloor #1 \rfloor}
\newcommand{\f}{\mathbb{F}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\parl}{\parallel}
\newcommand{\md}[1]{\left|#1\right|}
\newcommand{\ldju[2]}{\bigcup_{#1}^{#2}\hspace{-9mm\cdot}\hspace{7mm}}
\newcommand{\F}{\mathbb{F}}
\newcommand{\C}{\mathcal{C}}
\begin{document}
\lecture{}{V. Arvind}{Bireswar Das}{Ramprasad Saptharishi}
\section{Introduction}
``Expander Codes'' for a subclass of ``Low Density Parity Check''
codes. They are linear codes, which have rates and minimum distance
measures very close to optimal. Added to these nice properties, they
have very efficient decoding algorithms, in this lecture we shall see
one linear time decodable expander code and a linear time parallelly
decodable expander code.
\section{Linear Codes: Recall}
\begin{definition}
A linear code, $\C$, is a subspace of $\F_q^n$ of dimension $k$. This
also referred to a $[n,k]$ linear code. The code can also be thought
of a mapping from $\F_q^k$ to $\F_q^n$, expanding $k$ column vectors
to $n$ column vectors. $k$ is also referred to as the block size of
the code.
\end{definition}
\begin{definition}
An $k\times n$ matrix $G$ is called the generating matrix of a
$[n,k]$ linear code $\C$ if the rows of $G$ for a basis for $\C$.
\end{definition}
And since this generator matrix defines a linear transformation from
$\F_q^k \rightarrow \F_q^n$, the linear transformation can be thought
of as the encoding function for $k$-column vectors into $n$-space. \\
\noindent
Also, we can think of $\C$ as a kernel of a homomorphism,
\begin{eqnarray*}
H &:& \F_q^n \rightarrow \F_q^{n-k}\\
\C & = & \{x:Hx^T = 0\}
\end{eqnarray*}
The matrix $H$ forms a basis of the orthogonal complement of $\C$ and
is called the parity check matrix of $\C$.
\begin{definition}
The minimum distance $(\rho)$ for any code $\C$ is defined as the
least hamminng distance between any two codewords,
$$
\rho = \min_{x,y} \Delta(\C(x),\C(y))
$$
\end{definition}
And for any linear code, $\rho = \min_x wt(\C(x))$
\section{Bipartite Expanders and Expander Codes}
\begin{definition}
A bipartite graph $G = (V_L \cup V_R, E)$ is called a $(c,d)$-regular
graph if every vertex in $V_L$ has degree $c$ and every vertex in
$V_R$ has degree $d$.
\end{definition}
We shall be referring to the vertices on the left as ``variables'' and
those on the right as ``constraints''. The edges from $x$ on the left
to $y$ on the right will be interpretted as if the $y$ depends on
variable $x$.
\begin{definition}
A $(c,d,\epsilon, \delta)$-expander is a $(c,d)$-regular graph such
that for every $S\subseteq V_L$ such that $|S| \leq \epsilon |V_L| \implies
|\Gamma(S)| \geq \delta |S|$
\end{definition}
Let $B$ be a $(c,d)$-regular graph, with $V_L = \{v_1, \cdots, v_n\}$
variables and $V_R = \{p_1, \cdots, p_{m}\}$ with $m = \frac{cn}{d}$.
And similar to the rotation maps, we define a map
$b:\left[\frac{cn}{d}\right]\times [d] \rightarrow V_L$ such that
$b(i,j)$ returns the $j$-th neighbour of vertex $i \in V_R$
\begin{definition}Let $S$ be an error correcting code of block length
$d$. The expander code $\C(B,S)$ consists of all code words $[x_1,
\cdots, x_n]$ such that for all $i\in \left[\frac{nc}{d}\right]$
$$
\left[x_{b(i,1)}, x_{b(i,2)}, \cdots, x_{b(i,d)}\right] \in S
$$
\end{definition}
\begin{lemma}
Suppose $B$ is a $\parn{c,d,\alpha, \frac{c}{d\epsilon}}$-expander and
$S$ is a code with rate $r$ greater than $\frac{c-1}{c}$ and minimum distance
$\epsilon$, then the expander code $\C(B,S)$ has
\begin{itemize}
\item rate$(\C) \geq cr - (c-1)$
\item minimum relative distance $\rho(\C) \geq \alpha$.
\end{itemize}
\end{lemma}
\begin{proof}
Let $H$ be the parity check matrix of $S$; $H$ will be a $(d-k)\times
d$ matrix where $r=\frac{k}{d}$. Each constraint imposes $(1-r)d = d -
k$ linear restrictions. Hence the total number or linear restrictions
from all the constraints is atmost
$$
\frac{nc}{d}(1-r)d = cn(1-r)
$$
Hence the total degrees of freedom is atleast $n - cr(1-r)$. And hence
\begin{eqnarray*}
dim(\C) &\geq& n - nc(1-r)\\
\text{rate}(\C) & \geq & 1 - c(1-r)\\
& = & cr - (c-1)
\end{eqnarray*}
Suppose the minimum relative distance is not $\alpha$, then there
exists a codeword $w$ such that $wt(w) < \alpha n$. Let $V_w$ be
the set of indices $i$ such that $w_i=1$; $|V_w| < \alpha n$. The
total number of edges coming out of $V_w$ is $c|V_w|$. And by our size
bound on $|V_w|$ and the definition of expansion,
$|\Gamma(V_w)| > |V_w|\frac{c}{d\epsilon}$. Hence the average number
of edges per constraints is $< d\epsilon$, and therefore should exists
a constraint which has less than $d\epsilon$ neighbours in $V_w$. But
by the definition of minimum relative distance, every code word in $S$
{\em must} have atleast $d\epsilon$ ones, which gives us the required
contrdiction.
Hence, minimum relative distance of $\C$ is atleast $\alpha$.
\end{proof}
\section{``Easily'' Decodable Expander Codes}
In this section we shall look as two choices of our base code $S$ to
construct an expander code with very efficient decoding algorithms.
\subsection{The Even-Parity Expander Code}
\begin{definition}
The even parity code of block length $d$ is the set of all code
words $x$ such that
$$
\sum_{i=1}^d x_i \equiv 0\pmod 2
$$
\end{definition}
The dimension of the even-parity code of block length $d$ is $d-1$ and
hence the rate is $(d-1)/d$, and the minimum relative distance is
$\epsilon = 2/d$. \\
Let $B$ be a $(c,d)$-regular expander whose expansion parameters shall
be fixed soon, and let $S$ be the even parity code. If $B$ were a
$(c,d,\alpha, x)$ expander, we would need $x$ to be atleast $c/2$ for
the expander code to have minimum relative distance of $\alpha$. But
in order to be able to decode efficiently, we need more than $c/2$
expansion, we would need $3c/4$.
\subsubsection*{Decoding Algorithm:}
Input: A corrupted assignment $x$ on the variables.
\noindent
Algorithm:
\begin{itemize}
\item If there exists a variable $v$ that is incident to more
unsatisfied constraints than satisfied, flip its value.
\item Repeat until no more flips are possible.
\end{itemize}
\begin{claim}
The algorithm runs in linear time
\end{claim}
\begin{proof}
Clearly at every flip the number of satisfied constraints come down by
$1$ and hence this has to stop after linear number of flips. We only
need to argue that every flip takes only constant number of steps.
Let $S_0, S_1, \cdots, S_c$ be sets such that
$$
S_i = \{v|v\text{ has $i$ unsatisfied constraints}\}
$$
Pick a variable $v$ from the right-most non-empty set (most number of
unsatisfied constraints), say $S_i$; a flip is possible only if $i
>\frac{c}{2}$. If $v$ was flipped, the only variable that could get
affected would be those that are at a distance $2$ from $v$, and there
are atmost $cd$ of them. Hence, we would have to move atmost $cd$ many
variables from one $S_j$ to another, and this takes only constant
time.
Hence the algorithm runs in time $O(size(B))$.
\end{proof}
We now need to show that the above ``Decoding'' Algorithm {\em
decodes} considerable errors.
\begin{lemma}
If $B$ is a $\parn{c,d,\alpha, \frac{3c}{4}}$, the decoding algorithm corrects upto a $\alpha/2$ fraction of errors.
\end{lemma}
\begin{proof}
Suppose $w$ is the corrupted codeword and $w_0$ is the nearest
codeword. A variable where $w$ and $w_0$ don't match shall be
referred to as the corrupt variable, let $X$ be the set of corrupt
variables of $w$. Define the ``stage'' of the algorithm at any stage
as a tuple $(u,v)$ where $u$ is the number of unsatisfied
constraints and $v$ is the number of corrupt variables; we want $v$
to become $0$.\\
Let us first consider the stages where $v\leq \alpha u$. Let $s$ be
the number of satisfied neighbours of $X$. $|\Gamma(X)| = u+s >
(3c/4)v$ Each satisfied constraints should be connected to
atleast $2$ elements of $X$ (since $X$ is a set of corrupt
variables, a non-zero even number of flips should have happened),
and each unsatisfied constraint must be connected to atleast 1
element of $X$. And hence, the number of edges going out $=cv \geq u
+ 2s$. With this, and the earlier inequality that $u+s >
(3c/4)v$, we get $u > cv/2$. And now by our averaging argument,
there will exist one variable that will be flipped since half or
more of it's neighbours are unsatisfied, hence the algorithm
will flip some corrupt variable.\\
Now we shall show that the algorithm will successfully decode to the
nearest codeword if we begin with atmost $\alpha n/2$ corrupt
variable. The only way it can flip an uncorrupt variable is when $v
> \alpha n$. Hence if this were to happen, there should be some
point when $v = \alpha n$. But at this point, the earlier
inequalities work and it would tell us that $u> cv/2 > c\alpha n
/2$. But initially $u$ is atmost $c\alpha n/2$ and throughout the
algorithm this can only decrease, which leads to a contradiction.
Hence the algorithm will decode correctly if there are atmost
$\alpha n/2$ corrupt variables.
\end{proof}
\subsection{Explicit Constructions of Expander Codes}
Let $G=(V,E)$ be a $(n,d,\lambda)$ spectral expander ($\lambda$ is the
second largest eigenvalues of the un-normalized adjacency
matrix). From this a bipartite expander can be constructed by the
``mid-point'' partition.
For every $e\in E$, add a vertex for that edge and attach that vertex
to both the end points of the edge. Hence your new vertex set will be
$E\cup V$ and you have $B$, a $(2,d)$-regular graph. \\
Let $S$ be an error correcting code of block length $d$ with
$\epsilon$ as the minimum relative distance and $r$ as the rate. Hence
our expander code $\C(B,S)$ will have rate $\geq 2r - 1$.
\begin{theorem}[Alon, Chung]
Let $G$ be a $d$ regular spectral expander with $\lambda$ as its second largest
eigenvalue of the un-normalized adjacency matrix. Let $X\subseteq V$,
$|X| = \gamma |V|$. Then the number of edges in the subgraph induced
by $X$ is atmost
$$
\frac{d|V|}{2}\parn{\gamma^2 + \frac{\lambda}{d}\parn{\gamma - \gamma^2}}
$$
\end{theorem}
We would be using this theorem to prove the following claim about the
expander code.
\begin{claim}
The minimum relative distance of $\C{B,S}$ is atleast
$$
\parn{\frac{\epsilon - \frac{\lambda}{d}}{1 - \frac{\lambda}{d}}}^2
$$
\end{claim}
\begin{proof}
Suppose there exists a $w$ such that
$$
wt(w) \leq \frac{dn}{2}\parn{\gamma^2 + \frac{\lambda}{d}(\gamma - \gamma^2)}
$$
then by the theorem $w$ must be adjacent to greater than $\gamma n$
constraints. Since each constraint has $2$ neighbours, the average
number of variables per constraints is
$$
\frac{2\frac{dn}{2}\parn{\gamma^2 + \frac{\lambda}{d}(\gamma -
\gamma^2)}}{\gamma n}
$$
Thus if
$$
d\parn{\gamma^2 + \frac{\lambda}{d}(\gamma - \gamma^2)}<\epsilon d
$$
then a word of relative weight $\parn{\gamma^2 +
\frac{\lambda}{d}(\gamma - \gamma^2)}$ cannot be a codeword of
$\C(G,S)$ and this inequality is satisfied for
$$
\gamma < \parn{\frac{\epsilon - \frac{\lambda}{d}}{1 - \frac{\lambda}{d}}}
$$
Hence, in particular (relaxing the inequalities), there can't be a
non-zero codeword of weight $< \frac{dn}{2}\gamma^2$, and hence the
minimum relative distance of $\C(G,S)$ is atleast
$\parn{\frac{\epsilon - (\lambda/d)}{1 - (\lambda/d)}}^2$.
\end{proof}
\subsubsection*{Parallel Decoding Algorithm}
\begin{enumerate}
\item If for any constraint, the variables in that constraint differ
in atmost $\frac{d\epsilon}{4}$ places from the nearest codeword,
send a ``FLIP'' message to that vertex.
\item If a variable $v$ receives atleast one ``FLIP'', flip it's
value.
\item Repeat this round.
\end{enumerate}
\begin{claim}
If $\alpha$ fraction variables be corrupt relative to the nearest
codeword, then after one round of the parallel algorithm, then
fraction of corrupt variables (relative to the same codeword) is
atmost
$$
\alpha\parn{\frac{2}{3} + \frac{16\alpha}{\epsilon^3}+
\frac{4\lambda}{\epsilon d}}
$$
\end{claim}
\begin{proof}
Let $G$ be the $d$-regular graph from which $B$ was derived, so
$\C(B,S)$ has $\frac{dn}{2}$ variables and $n$ constraints. Let $X$
be the set of $\frac{\alpha nd}{2}$ corrupt variables. The variables that
remain corrupt at the end of one round are those that don't receive a
``FLIP'' message. We shall call a constraint ``confused'' if it sends
a ``FLIP'' message to something that's not in $X$, and we shall call a
constraint ``unhelpful'' if it is adjacent to a vertex in $X$ but does
not send a ``FLIP'' message to it.
For a constraint to be confused, atleast $\frac{3d\epsilon}{4}$
variables from $X$ must be its neighbours. And since each variable of
$X$ is a neighbour of $2$ constraints, the number of confused
constraints is atmost
$$
\frac{2\frac{\alpha dn}{2}}{\frac{3\epsilon d}{4}} = \frac{4\alpha n}{3\epsilon}
$$
Each of these can send atmost $\frac{d\epsilon}{4}$ ``FLIP'' signals
and hence the number of variables outside $X$ that would receive
``FLIP'' signals is atmost
$$
\frac{4\alpha n}{3\epsilon} \frac{d\epsilon}{4} =
\frac{dn}{2}\cdot\frac{2\alpha}{3}
$$
For a constraint to be unhelpful, it must have more than
$\frac{d\epsilon}{4}$ neighbours in $X$. And hence the number of
unhelpful constraints is atmost
$$
\frac{2\frac{\alpha dn}{2}}{\frac{\epsilon d}{4}} = \frac{4\alpha n}{\epsilon}
$$
These constraints are vertices in our original graph and by Alon's
theorem, there can be atmost
$$
\frac{dn}{2}\parn{\parn{\frac{4\alpha}{\epsilon}}^2 + \frac{\lambda}{d}\parn{\frac{4\alpha}{\epsilon}}}
$$
variables such that both its neighbours are unhelpful (and hence
doesn't receive a ``FLIP'' message).
And hence, the fraction of corrupt variables at the end one round is atmost
$$
\alpha\parn{\frac{2}{3} + \frac{16\alpha}{\epsilon^3}+
\frac{4\lambda}{\epsilon d}}
$$
\end{proof}
And now with suitable choice of parameters now, we can show that this
decoding is also linear time. We shall choose $\alpha <
\frac{\epsilon^2}{48}$ and $\lambda = 2\sqrt{d-1}$, showing that the
algorithm is linear time for these parameters is left to the
interested reader. %comes in exam!
\end{document}