\documentclass[twoside]{article}
\textwidth=6in
\oddsidemargin=0.25in
\evensidemargin=0.25in
\topmargin=-0.1in
\footskip=0.8in
\parindent=0.0cm
\parskip=0.3cm
\textheight=8.00in
\sloppy
\usepackage{amssymb}
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{latexsym}
\usepackage{epsfig}
\def\hell{h_{\ell^{-1}}}
\begin{document}
\input{../preamble.tex}
\lecture{15}{October 30, 2002}{Madhu Sudan}{Yael Tauman}
%%%% body goes in here %%%%
\section{Introduction}
In this lecture, we present a local decoding algorithm and a local list-decoding algorithm
for Reed-Muller codes.
These algorithms are very interesting, since they played a significant
role in many developments in complexity theory over the
past two decades. For example, these algorithms were used in the following results.
\begin{itemize}
\item
``The permanent of a matrix is hard to compute on random matrices'',
due to Lipton~\cite{Lipton}.
(This result makes use of a simple unambiguous decoding algorithm
for Reed-Muller codes implicit, in Beaver and Feigenbaum~\cite{BeaverF}).
\item
``IP = PSPACE~\cite{LFKN,Shamir}'',
``MIP=PSPACE~\cite{BFL}'' and
the ``PCP Theorem~\cite{AroraSafra,ALMSS}''.
\item
The sequence of results showing progressively
weaker complexity-theoretic conditions that would suffice to show
``BPP = P''~\cite{NW,BFNW,IW}.
\end{itemize}
The algorithms in today's lecture are very simple, and do not
exploit any serious algebraic property. The only algebraic elements that
the algorithms use are decoding algorithms for Reed-Solomon codes, and we'll just adopt
them as a black box from a previous lecture.
We'll describe the algorithms in three steps - first we
give an algorithm that decodes from a very low error rate.
%(much less than half the minimum distance).
Then we show how, using a Reed-Solomon decoder, one can recover from a slightly larger error rate.
Finally, we jump to a list-decoder, which uses a Reed-Solomon list-decoder,
and can recover from a much larger error rate.
Let us first recall the definition of Reed-Muller
codes (defined in lecture 4).
Recall that these are the generalization of Reed-Solomon
codes to multivariate polynomials.
\begin{definition}
[Reed-Muller Codes]
A Reed-Muller code, $\RM_{m,d,q}$, is the code whose codewords
are evaluations of $m$-variate polynomials of total degree at
most $d$,
over all elements in ${\mathbb F}_q$.
\end{definition}
The $\RM_{m,d,q}$ code is a linear code with $n=q^m$,
$k=\binom{m+d}{d}$, and with relative distance
$\left(1-\frac{d}{q}\right)$ when $d \leq q$ (follows from the "Schwartz Lemma").
For today's lecture, it is
convenient to think of the decoding task as a ``function
reconstruction task'' rather than as a task of
reconstructing a vector or string representing
the codeword. We will thus think of the received word
being given by some function $f:\F_q^m \to \F_q$, and
our goal is to output a codeword (or a list of all nearby codewords),
where the codewords are also functions $p:\F_q^m\to\F_q$.
For any two functions $f$ and $g$, let
$$
\delta(f,g) = \Pr_{\vec x \in \F_q^m}[f(x) \ne g(x)].
$$
Note that, if $f$ and $g$ are interpreted
as strings rather than functions,
this is just the standard Hamming distance normalized so
as to be between $0$ and $1$.
\begin{quote}
{\bf Reed-Muller Decoding:} \\
{\sc Given:} Oracle access to a function $f:\F_q^m\to \F_q$,
a degree parameter $d$ and a disagreement parameter $\delta$.\\
{\sc Task:} A (list of all) degree $d$ polynomials
$p:\F_q^m\to\F_q$ such that $\delta(f,p) \leq \delta$.
\end{quote}
We will present randomized algorithms that, given any vector
$\vec a \in \F_q^m$, compute $p(\vec a)$ in time $\poly(m,d,q)$.
Note that the length of the codewords is $\binom{m+d}{d}$,
which could be exponentially larger than $\poly(m,d,q)$,
and hence the our algorithms are much more efficient than explicit decoding algorithms.
\section{Decoding from very low error}
\label{l15:rsr}
We start with describing an extremely simple randomized
algorithm that
recovers from a very low error rate $\delta$. The amount of error will certainly
be small enough to put us in the case of an unambiguous decoding
problem. So the polynomial $p$ that is $\delta$-close to $f$
is unique. Our algorithm will try to guess the value $p(\vec a)$,
by looking at $f$ on a small random sample of values. The trick
is in picking the right ``random sample''. We will look
at $f$ on a ``line'' in $\F_q^m$.
\subsection{Lines in $\F_q^m$}
\begin{definition}
The line $\F_q^m$ through a point $\vec a$
with slope $\vec b$ is the set of points:
$$
\ell_{\vec a, \vec b}:=\{ \vec a +
t \vec{b} \mid t \in \F_q\}.
$$
\end{definition}
In the definition above, we thought of a line as an
unordered set of points.
However, it is also useful to think of a line as a
function $\ell_{\vec a,\vec b}:\F_q\to\F_q^m$, given
by $\ell_{\vec a,\vec b}(t) = \vec a + t \vec b$.
Let us point out two nice properties of
lines.
\begin{enumerate}
\item{{\bf Randomness Property:}}
The first nice property of a line is its randomness
property.
%We first define the notion of a random line
%and a random line through a point $\vec a \in \F_q^m$.
%\begin{definition}
%For a point $\vec a \in \F_q^m$, a random line through
%$\vec a$ is the random variable $\ell_{\vec a, \vec b}$
%where $\vec b$ is picked uniformly from $\F_q^m$.
%A random line in $\F_q^m$ is the random variable
%$\ell_{\vec a, \vec b}$ where both $\vec a$ and $\vec b$
%are chosen independently and uniformly at random from
%$\F_q^m$.
%\end{definition}
\begin{itemize}
\item{(Pairwise Independence):}
A random line through $\F_q^m$ is a collection of
pairwise independent points in $\F_q^m$. I.e., for
$t_1 \ne t_2 \in \F_q$, the points $\ell_{\vec a,\vec b}(t_1)$
and $\ell_{\vec a,\vec b}(t_2)$ are distributed
independently and uniformly in $\F_q^m$.
\item{($1$-wise Independence):}
For every $\vec a$, every non-zero point on
a random line through $\F_q^m$ is a random point.
I.e., for every $t \in \F_q - \{0\}$, the point
$\ell_{\vec a, \vec b}(t)$ is distributed uniformly
in $\F_q^m$, when $\vec b$ is distributed uniformly
in $\F_q^m$.
\end{itemize}
\item{{\bf Algebraic Property}:}
This property alludes to the restriction of functions to
lines. Note that when the line is viewed as a function
$\ell:\F_q \to \F_q^m$, then it composes naturally with
a function $f:\F_q^m \to \F_q$ to give a ``univariate
function'' $f|_\ell : \F_q \to \F_q$, given by
$f|_\ell(t) = f(\ell(t))$.
\begin{itemize}
\item
For every degree $d$ polynomial $p:\F_q^m\to\F_q$ and
every line $\ell:\F_q\to \F_q^m$,
the function $p|_\ell$ is a univariate polynomial of
degree at most $d$.
\end{itemize}
\end{enumerate}
\subsection{The algorithm}
Our first algorithm for decoding Reed-Muller codes is
an elementary algorithm that uses the above two properties of
lines in $\F_q^m$.
This algorithm, given oracle access to a function
$f:\F_q^m\to\F_q$ that is very close to a degree $d$ polynomial
$p:\F_q^m\to\F_q$, and given an element $\vec a\in\F_q^m$,
outputs $p(\vec a)$
with probability greater than, say, $2/3$, over
its internal coin tosses. Repetition followed by a plurality
vote suffices to reduce this error probability. Once the error
probability reduces to say less than
$\frac13 q^{-m}$, then repeating this trial for every choice of
$\vec a$ produces the correct codeword with probability at least
$\frac23$.
The basic idea to compute $p(\vec a)$ is to focus on just
a random line $\ell$ through $\vec a$ and to reconstruct
the function $p|_{\ell}$. From the algebraic property,
$p|_{\ell}$ is a univariate polynomial of degree $d$.
>From the randomness property, $p|_{\ell}$ and $f|_{\ell}$ have good agreement.
So $p|_{\ell}$ can hopefully be recovered efficiently. Once
this is done, all we need to do is output $p_{\ell}(\vec a)$.
Below we describe and analyze the most elementary form of this
idea. In this form, the algorithm only needs $q \geq d+2$
to work. However, the amount of error it will correct is quite small.
\begin{description}
\item[Simple RM decoder:]
\item[Given:] Oracle access to $f:\F_q^m\to\F_q$, a point
$\vec a \in \F_q^m$ and a degree parameter $d$.
\item[Promise:] There exists a degree $d$ polynomial
$p:\F_q^m\to\F_q$ such that
$\delta = \delta(p,f) \leq \frac{1}{3(d+1)}$.
\item[Goal:] Output $p(\vec a)$.
\item[Step 1:] Pick $\vec b \from \F_q^m$ at random and let
$\ell = \ell_{\vec a,\vec b}$.
\item[Step 2:] Let $\alpha_1,\ldots,\alpha_{d+1}$ be distinct
elements in $\F_q - \{0\}$. For $i \in [d+1]$, let $\beta_i =
f(\vec a + \alpha_i \vec b)$.
\item[Step 3;] Interpolate to find a degree $d$ univariate polynomial
$h$ such that $h(\alpha_i) = \beta_i$ for every $i \in [d+1]$.
\item[Step 4:] Output $h(0)$.
\end{description}
Note that Step 2 above requires $q\geq d+2$. We will show below that
this requirement suffices for correctness, provided the
error is small enough.
\begin{lemma}
\label{l15:simple-lemma}
Under the assumption $\delta = \delta(f,p) \leq \frac{1}{3(d+1)}$, the
algorithm {\bf Simple RM decoder} outputs $p(\vec a)$ with
probability at least $\frac23$.
\end{lemma}
\begin{proof}
We define $d+1$ ``bad'' events $B_i$ over the random choice
of $\vec b$.
We show that if none of these events occurs, then the algorithm
correctly outputs $p(\vec a)$.
Then we show that the probability that none
of these events occurs is at least $1 - (d+1)\delta$.
Note that the Lemma follows once this is shown.
We define the event $B_i$ to be the case
``$\beta_i \ne p|_{\ell}(\alpha_i)$''.
Note that if none of these events occur, then we know the
value of the function $p|_{\ell}(\cdot)$ at $d+1$ distinct
values in $\F_q$. Furthermore, the algebraic property implies that
$p|_{\ell}$
is a polynomial of degree at most $d$. Thus, the polynomial
$h$ found in Step 3 {\em is} the function $p|_{\ell}$,
and hence the value output in Step 4 is
$p|_{\ell}(0) = p(\ell(0)) = p(\vec a)$.
So it suffices to bound the probability of the bad events.
Note that $B_i$ happens if and only if $f(\ell(\alpha_i)) \ne
p(\ell(\alpha_i))$. The randomness property implies that
$\ell(\alpha_i)$ is a random point in $\F_q^m$ and hence
the probability that $f$ does not agree with $p$ at this point
is exactly $\delta(f,p)$. Thus, we have that the probability of
$B_i$ is $\delta$. By the union bound, the probability that
at least one of the bad events occurs is at most $(d+1)\delta$.
The probability that none of them occurs is at least $1 - (d+1)\delta$.
This concludes the proof.
\end{proof}
Note that the algorithm is quite efficient --- it runs in time
$\poly(m,d)$, while the codeword has length $\binom{m+d}{d}$ which
could be exponentially larger. Of course, it does not recover all
the codeword at once --- this is simply impossible in this much time;
but it can recover any coordinate of the codeword in such time.
Note that with the following choice of parameters, we get a Reed-Muller code
with polynomial rate and constant distance, that can correct a poly-logarithmic
fraction of errors.
\begin{itemize}
\item
$d=(\lg k)^c$
\item
$m=\frac{\lg k}{(c-1)\lg\lg k}$\\
\\
(Verify that $\binom{d+m}{m}\approx k$).
\item
$q=2(d+2)$
\item
$n=q^m\approx (2d)^m\approx k^{1+\frac{1}{c-1}}$
\end{itemize}
\section{Improving the error-correction capability}
\label{l15:glrsw}
We would like to improve the error-correction capability of
the simple algorithm described in the previous section.
Increasing the error-correction capability comes
at a price: The requirement on the field size goes up, and
the algorithm gets slightly more complicated.
To motivate the basic idea behind the improvement, let us look
back at the reason why the error correction capability was so
low ($\Theta(1/d)$) in the algorithm of the last section.
The reason we lost so much was that we required that $d+1$ queries
on a random line through $\vec a$ should {\em all} be error-free.
To improve the performance, we will make a few more queries, but then
allow for the possibility that a few answers are incorrect.
The polynomial $p|_{\ell}$ will then be the polynomial that ``usually''
agrees with the queried values --- this polynomial can be found by
a Reed-Solomon decoding step.
The number of queries that the algorithm makes depends
on the rate of error we wish to correct, on the running time we desire,
and on the field size. We will set this number, somewhat arbitrarily,
to $5(d+1)$ and demonstrate the effect.
\begin{description}
\item[Improved RM decoder:]
\item[Given:] Oracle access to $f:\F_q^m\to\F_q$, a point
$\vec a \in \F_q^m$ and a degree parameter $d$.
\item[Promise:] There exists a degree $d$ polynomial
$p:\F_q^m\to\F_q$ such that
$\delta = \delta(p,f) < \frac{1}{5}$.
\item[Goal:] Output $p(\vec a)$.
\item[Step 1:] Pick $\vec b \from \F_q^m$ at random and let
$\ell = \ell_{\vec a,\vec b}$.
\item[Step 2:] Let $\alpha_1,\ldots,\alpha_{5(d+1)}$ be distinct
elements in $\F_q - \{0\}$. For $i \in [5(d+1)]$, let $\beta_i =
f(\vec a + \alpha_i \vec b)$.
\item[Step 3;] Find a degree $d$ univariate polynomial
$h$ such that $h(\alpha_i) = \beta_i$ for at least $3(d+1)$
choices of $i \in [5(d+1)]$.
\item[Step 4:] Output $h(0)$.
\end{description}
All steps above are efficient. In particular, Step 3 can be executed
in $\poly(d)$ time by using an unambiguous Reed-Solomon decoding algorithm
(such as the Welch-Berlekamp algorithm described in a
previous lecture). We thus get the following proposition.
\begin{proposition}
{\bf Improved RM decoder} runs in $\poly(d,m)$ time.
\end{proposition}
\begin{lemma}
Under the assumption $\delta = \delta(f,p) < \frac{1}{5}$, the
algorithm {\bf Simple RM decoder} outputs $p(\vec a)$, with
probability greater than $\frac12$.
\end{lemma}
\begin{proof}
As in the proof of Lemma~\ref{l15:simple-lemma}, we define
for every $i \in [5(d+1)]$,
$B_i$ to be the event ``$\beta_i \ne p|_{\ell}(\alpha_i)$''.
Note that for every $i$ the probability of $B_i$ is exactly $\delta$.
Now let $B$ be the event that $B_i$ is true for more than $2(d+1)$
choices of $i$. The probability that $B$ occurs can be upper bounded,
using Markov's inequality, by ${5\delta(d+1)}/{2(d+1)}=5\delta/2$.
Note that if $B$ does not occur, then $p|_{\ell}$
agrees with the points
$\{(\alpha_i,\beta_i)~\mid~i \in [(5(d+1)]\}$ on
$3(d+1)$ points and hence is the unique solution in Step 3, and thus,
in Step 4 we output $p|_{\ell}(0) = p(\vec a)$. Hence, to achieve
error probability less than $\frac 12$, we need $5\delta/2<1/2$,
which happens for $\delta<1/5$.
\end{proof}
The ideas in the algorithm above can be pushed further to get
a decoding algorithm for $\delta<1/4$. It is known that we cannot achieve
a decoding algorithm for $\delta\geq 1/4$, using Markov's inequality.
\section{A List Decoding Algorithm}
\label{l15:list-decode}
Part of the reason why the algorithms from the previous section
could not correct too many errors is that they never exploited
the ability to list-decode the Reed-Solomon codes (in Step $3$).
If we did, we would be able to find polynomials with much smaller
agreement with $f$ on any given line $\ell$. However,
what should we do with a list of univariate polynomials that
agree with $f$ on $\ell$? How do we find out which one is the
polynomial ``$p$''? In fact, what is $p$?
In previous sections $p$ was uniquely specified as the nearest
polynomial (codeword) to the function $f$ (the received vector).
Now that we are hoping to perform list-decoding, there is a list
of polynomials that could have the desired agreement.
We will solve this problem by focussing on one of the specific polynomials $p$ that is close
to $f$. This will be done by giving a small amount of additional information, called
{\em advice}, that suffices to specify it uniquely. We will then
give a reconstruction procedure that computes $p(\vec a)$ given
$\vec a$. By varying the advice, we'll then be able to compute all
the polynomials close to $f$.
So what is the advice that we'll use to specify $p$? It turns out
that with high probability,
the value of $p$ at one, randomly chosen point $\vec b \in \F_q^m$,
specifies it uniquely, provided $q$ is large enough relative to
$\delta$ and $d$. As usual, when it comes to list-decoding, it is
more informative to focus on the amount of agreement rather than
the amount of disagreement between $f$ and the polynomial $p$.
Define
$$
\tau(f,g) = \Pr_{\vec x \from \F_q^m} [ f(x) = g(x) ]
$$
to be the {\em agreement} between $f$ and $g$.
We start with the following simple proposition that proves that,
with high probability,
the value of a polynomial at a random point specifies it uniquely,
given a nearby function $f$.
\begin{proposition}
\label{l15:agree}
Let $p_1,\ldots,p_n$ be a list of all $m$-variate degree $d$
polynomials over $\F_q$ satisfying $\tau(f,p_i) \geq \tau$.
If $\tau \geq \sqrt{2d/q}$ then $n \leq 2/\tau$, and
with probability at least $1 - \binom{n}2 (\frac{d}q) \geq
1 - \frac{2d}{\tau^2 q}$ over
the choice of $\vec z \in \F_q^m$ it is the case that
the sequence of elements $\langle p_1(\vec z),
\ldots,p_n(\vec z) \rangle$ are all distinct.
\end{proposition}
\begin{proof}
The first part of the proposition, claiming $n \leq 2/\tau$ is
just recalling the Johnson bound from a previous lecture.
The second part follows from an application of the union
bound to the $\binom{n}2$ possible ``bad'' events $B_{ij}$,
$1 \leq i < j \leq n$,
where $B_{ij}$ is the event ``$p_i(\vec z) = p_j(\vec z)$''.
Note that $B_{ij}$ occurs with probability at most
$\frac dq$ (by the ``Schwartz
Lemma'').
\end{proof}
This motivates the idea of the next algorithm. We will assume
that we are given one useful piece of information --- namely the
value of $p$ at one (randomly chosen) point $\vec z \in \F_q^m$.
Say $p(\vec z) = \gamma$.
Now suppose we wish to reconstruct the value of $p$ at
$\vec a \in \F_q^m$.
We will execute the algorithm of the previous section and pick a
line $\ell$ through $\vec a$. Suppose we are fortunate enough that
$\vec z$ lies on $\ell$. In this case, given a list of polynomials
$h_1,\ldots,h_n$ that have non-trivial agreement with $f$ on $\ell$,
we can determine which one is $p|_{\ell}$ by considering the values
$h_i(\vec z)$. Hopefully they are all different and then the
polynomial $h_i$ for which $h_i(\vec z) = \gamma$ is $p|_{\ell}$.
$h_i(\vec a)$ is then the value we are seeking. The only catch
is that a random line will no longer work - it is very unlikely
to pass through $\vec z$. We will fix this by deterministically
picking the line that passes through $\vec z$!
The algorithm is described for a fixed choice of $\vec z$
and advice $\gamma$.
\begin{description}
\item[List-decoding procedure $A_{\vec z, \gamma}$]
\item[Given:] Oracle access to $f$, a point $\vec a \in \F_q^m$, a degree
parameter $d$,
and an agreement parameter $\tau$.
\item[Step 1:] Let $\vec b = \vec z - \vec a$ and let
$\ell = \ell_{\vec a,\vec b}$.
(Note that $\ell(0)=\vec a$ and $\ell(1)=\vec z$).
\item[Step 2:] Find all degree $d$ univariate polynomials
$h_1,\ldots,h_n$ such that $h_i(\alpha) = f(\ell(\alpha))$ for
at least $\frac{\tau}{2}q$ choices of $\alpha \in \F_q$.
\item[Step 3:] If there exists a unique index $i \in [n]$
such that $h_i(\vec z) = \gamma$, output $h_i(0)$, else
output {\sf error}.
\end{description}
We start by noticing that all steps require a polynomial running time,
provided the parameters are favorable. In particular, Step $2$
can be executed in polynomial time assuming $\frac{\tau}2 >
\sqrt{d/q}$ using the improved List-decoding algorithm
for Reed-Solomon codes from a previous lecture.
\begin{proposition}
If $\tau > \sqrt{4d/q}$ then the subroutine $A_{\vec z,\gamma}$
runs in time $\poly(q,m)$.
\end{proposition}
Next we analyze the correctness of the algorithm.
Note that $A_{\vec z, \gamma}$ is a deterministic algorithm.
We will analyze it only for a random $\vec a$. That is,
We show that for a random pair $(\vec z, \vec a)$, if $\tau(p,f)\geq\tau$,
then the algorithm
$A_{\vec z, p(\vec z)}$ is very likely to output $p(\vec a)$.
We conclude that there exists a vector $\vec z$ (in fact most
choices would work) such that $A_{\vec z, p(\vec z)}$ computes
a function very close to $p$. This is not what we want --- we want
an algorithm that always computes $p$. However the algorithms
of the previous section can now be applied to $A_{\vec z,p(\vec z)}$
to get a randomized algorithm that computes $p$ correctly everywhere
with high probability. Thus, the following lemma will be quite
sufficient for our purposes.
\begin{lemma}
\label{l15:list-one}
Let $p$ be a polynomial which agrees with $f$ on a $\tau$ fraction of the inputs.
Then, for any $\epsilon > 0$, and for random
$\vec z, \vec a \in \F_q^m$, $A_{\vec z, p(\vec z)}$ outputs
$p(\vec a)$ with probability at least $1- \epsilon$, assuming
$q \geq \frac{16(d+1)}{\tau^2 \epsilon}$.
\end{lemma}
\begin{proof}
As in previous proofs, we describe some bad events and then
claim that if none of the bad events occur, then the algorithm
$A_{z,p(\vec z)}$ outputs $p(\vec a)$. Our first bad event
$B$ is the event that ``$p$ and $f$ have less than $\tau/2$
agreement on $\ell$''.
Let $h_1,\ldots,h_n$ be all univariate polynomials that have
$\tau/2$ agreement with $f|_{\ell}$. The second bad event, $C$,
is the event that
there exists a pair $1 \leq i < j \leq n$ such that
$h_i(\vec z) = h_j(\vec z)$. We show below that if neither
$B$ nor $C$ occurs, then the algorithm $A_{\vec z, p(\vec z)}$
outputs $p(\vec a)$. Later we give upper bounds on the
probabilities of $B$ and $C$.
\begin{quote}
\begin{claim}
If neither of the events $B$ or $C$ occurs, then
$A_{\vec z, p(\vec z)}$ outputs $p(\vec a)$ on input $\vec a$.
\end{claim}
\begin{proof}
This is relatively straightforward. Since the event $B$ does not
occur, we have that the polynomial $p|_{\ell}$ has at least
$\tau/2$ agreement with $f$ on the line $\ell$. Thus, one of the
polynomials $h_1,\ldots,h_n$ computed by $A_{\vec z, p(\vec z)}$ in
Step $2$ is $p|_{\ell}$. Say it is the polynomial $h_i$. Then
$h_i(\vec z) = p(\vec z)$. But since the event $C$ did not occur,
we know that $h_j(\vec z) \ne h_i(\vec z)$ for any other
index $j$. Thus, $h_i$ is the unique polynomial satisfying the
condition of Step $3$ and hence Step $3$ results in the output $h_i(0)
= p(\vec a)$.
\end{proof}
\begin{claim}
The probability of event $B$, taken over the choices of $\vec z$
and $\vec a$, is at most $\frac{4}{\tau q}$.
\end{claim}
\begin{proof}
This is a simple application of the Chebychev inequality.
Since $\ell$ is a random line (for random $\vec z, \vec a \in \F_q^m$),
the randomness property implies that the points in the line
$\ell$ are distributed uniformly over $\F_q^m$ and are pairwise
independent. On any one point, the probability that $f$ agrees
with $p$ is $\tau$. Thus, the expected number of agreements
between $f$ and $p$ on all $q$ points in $\ell$ is
$\tau q$. Since these $q$ points are pairwise independent,
using the Chebychev inequality, we derive that
the probability that this number deviates from its
expectation by half the expectation is bounded by $\frac{4}{\tau q}$.
\end{proof}
\begin{claim}
The probability of event $C$, taken over the choice of $\vec z$
and $\vec a$, is at most $\frac{8d}{\tau^2 q}$, provided
$\tau > 2\sqrt{d/q}$.
\end{claim}
\begin{proof}
The claim would be obvious, following immediately from
Proposition~\ref{l15:agree}, if $\vec z$ was chosen to be
a random point on line $\ell$ after the line is fixed.
But this is not the case! Or is it?
In the way the algorithm is described, $\vec a$ and $\vec z$
are chosen first and then $\ell$ is defined based on them.
However we could pick $\ell$ at random first,
and then choose $\vec a$ and $\vec z$ at random from
$\ell$. Let $h_1,\ldots,h_n$ be all the univariate polynomials that have
$\frac{\eta}{2}$ agreement with $f|_{\ell}$.
Thus, the probability, when we pick $\vec z$ at random
from $\ell$, that $h_i(\vec z) = h_j(\vec z)$ for some distinct
pair $i,j$ is at most $\frac{8d}{\tau^2 q}$ (applying
Proposition~\ref{l15:agree} in the univariate case with agreement
set to $\tau/2$). The claim follows.
\end{proof}
\end{quote}
We are now ready to glue together the proof of the lemma.
We will pick $q$ large enough so that the two events above
happen with probability at most $\epsilon/2$ each. Thus
we get the condition $q \geq \max\{\frac{8}{\tau \epsilon},
\frac{16d}{\tau^2\epsilon}\}$. To make this simpler we set
$q \geq \frac{16(d+1)}{\tau^2 \epsilon}$.
Once we have this condition
we find that the probability that $B$ or $C$ occurs is at most
$\epsilon$
and with the remaining probability $A_{\vec z, p(\vec z)}$
outputs $p(\vec a)$.
\end{proof}
\section{Bibliographic Notes}
The simple algorithm for
decoding Reed-Muller codes from Section~\ref{l15:rsr} is based on
an algorithm of Beaver and Feigenbaum~\cite{BeaverF}, whose ability
to decode all polynomials was pointed out by Lipton~\cite{Lipton}.
The improvement in Section~\ref{l15:glrsw} is due to Gemmell et
al.~\cite{GLRSW}. Further improvements to this algorithm, decoding
arbitrarily close to half the minimum distance for $q \gg d$
were given by Gemmell and Sudan~\cite{GemmellS}. The list-decoding
algorithm in Section~\ref{l15:list-decode} is due to Sudan,
Trevisan, and Vadhan~\cite{STV}. This algorithm simplifies
a previous list-decoding algorithm of Arora and Sudan~\cite{AroraSudan}.
\bibliographystyle{plain}
\begin{thebibliography}{10}
\bibitem{ALMSS}
Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy.
\newblock Proof verification and the hardness of approximation problems.
\newblock {\em Journal of the {ACM}}, 45(3):501--555, May 1998.
\bibitem{AroraSafra}
Sanjeev Arora and Shmuel Safra.
\newblock Probabilistic checking of proofs: A new characterization of {NP}.
\newblock {\em Journal of the ACM}, 45(1):70--122, January 1998.
\bibitem{AroraSudan}
Sanjeev Arora and Madhu Sudan.
\newblock Improved low-degree testing and its applications.
\newblock In {\em Proceedings of the Twenty-Ninth Annual ACM Symposium on
Theory of Computing}, pages 485--495, El Paso, Texas, 4-6 May 1997.
\bibitem{BFL}
L{\'a}szl{\'o} Babai, Lance Fortnow, and Carsten Lund.
\newblock Non-deterministic exponential time has two-prover interactive
protocols.
\newblock {\em Computational Complexity}, 1(1):3--40, 1991.
\bibitem{BFNW}
L\'{a}szl\'{o} Babai, Lance Fortnow, Noam Nisan, and Avi Wigderson.
\newblock {BPP} has subexponential time simulations unless {EXPTIME} has
publishable proofs.
\newblock {\em Computational Complexity}, 3(4):307--318, 1993.
\bibitem{BeaverF}
Donald Beaver and Joan Feigenbaum.
\newblock Hiding instances in multioracle queries.
\newblock In C.~Choffrut and T.~Lengauer, editors, {\em Proceedings of the 7th
Annual Symposium on Theoretical Aspects of Computer Science}, pages 37--48,
Rouen, France, 22--24 February 1990. Springer.
\bibitem{BlumKannan}
Manuel Blum and Sampath Kannan.
\newblock Designing programs that check their work.
\newblock {\em Journal of the ACM}, 42(1):269--291, January 1995.
\bibitem{GLRSW}
Peter Gemmell, Richard Lipton, Ronitt Rubinfeld, Madhu Sudan, and Avi
Wigderson.
\newblock Self-testing/correcting for polynomials and for approximate
functions.
\newblock In {\em Proceedings of the Twenty Third Annual ACM Symposium on
Theory of Computing}, pages 32--42, New Orleans, Louisiana, 6-8 May 1991.
\bibitem{GemmellS}
Peter Gemmell and Madhu Sudan.
\newblock Highly resilient correctors for multivariate polynomials.
\newblock {\em Information Processing Letters}, 43(4):169--174, September 1992.
\bibitem{IW}
Russell Impagliazzo and Avi Wigderson.
\newblock {${\rm P}={\rm BPP}$} if ${E}$ requires exponential circuits:
{D}erandomizing the {XOR} {L}emma.
\newblock {\em Proceedings of the 29th Annual ACM Symposium on Theory of
Computing}, pages 220--229, May 1997.
\bibitem{Lipton}
Richard Lipton.
\newblock New directions in testing.
\newblock In {\em Distributed Computing and Cryptography}, volume~2 of {\em
DIMACS Series in Discrete Mathematics and Theoretical Computer Science},
pages 191--202. AMS, 1991.
\bibitem{LFKN}
Carsten Lund, Lance Fortnow, Howard~J. Karloff, and Noam Nisan.
\newblock Algebraic methods for interactive proof systems.
\newblock {\em Journal of the ACM}, 39(4):859--868, October 1992.
\bibitem{NW}
Noam Nisan and Avi Wigderson.
\newblock Hardness vs randomness.
\newblock {\em Journal of Computer and System Sciences}, 49(2):149--167,
October 1994.
\bibitem{Shamir}
Adi Shamir.
\newblock {IP = PSPACE}.
\newblock {\em Journal of the ACM}, 39(4):869--877, October 1992.
\bibitem{STV}
Madhu Sudan, Luca Trevisan, and Salil Vadhan.
\newblock Pseudorandom generators without the {XOR} lemma.
\newblock {\em Proceedings of the 31st Annual ACM Symposium on Theory of
Computing}, pages 537--546, 1999.
\end{thebibliography}
\end{document}