\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}