We will see a (non-local) efficient decoding algorithm for Reed-Solomon codes.
Let \(\mathbb F\) be the \(q\)-element field and let \(f\colon \mathbb F\to \mathbb F\) be a function (a corrupted evaluation of a degree-\(d\) polynomial). The goal is to find a degree-\(d\) polynomial \(P\in \mathbb F[x]_{d}\) that agrees with \(f\) as often as possible.
Theorem: If less than \((q-d)/2\) positions are corrupted, we can decode \(P\) in time \(\mathrm{poly}(q)\).
Proof:
First, suppose that there exists a degree-\(d\) polynomial \(P\) that perfectly agrees with \(f\). How can we find such a polynomial? One way to find \(P\) is to set up the following linear system (in the coefficients of \(P\)) and solve it using Gaussian elimination, \[ P(\alpha_1)=f(\alpha_1),\] \[\ldots\] \[P(\alpha_{q})=f(\alpha_{q}).\] (Here, \(\alpha_1,\ldots,\alpha_{q}\) is an enumeration of the elements of \(\mathbb F\).)
Next, suppose that \(f\) is corrupted in \(\tau\) positions. We will try to reduce to the case without errors! For sake of analysis, let \(E\in\mathbb F[x]_\tau\) be the degree-\(\tau\) polynomial that vanishes on the corrupted positions, i.e., \[ E = \prod_{\alpha\colon f(\alpha)\neq P(\alpha)} (x-\alpha). \]
Now, the polynomials \(N=F\cdot E\) and \(E\) satisfy the equation \(N(\alpha)=f(\alpha)\cdot E(\alpha)\) for every \(\alpha\in \mathbb F\). (We zeroed out the errors!)
Via Gaussian elimination, we can find non-zero polynomials \(N'\in \mathbb F[x]_{\tau+d}\) and \(E'\in \mathbb F[x]_\tau\) that satisfy the following linear constraints (on their coefficients), \[ N'(\alpha_1) = f(\alpha_1)\cdot E'(\alpha_1),\] \[ \ldots\] \[ N'(\alpha_q) = f(\alpha_q)\cdot E'(\alpha_{q}),\]
Finally, we want to show that \(P=N'/E'\) (in that case, we can compute \(P\) easily from \(N'\) and \(E'\)). In other words, we want to show that \(P\cdot E'-N'\) is the zero polynomial. On the one hand, the degree of this polynomial is at most \(\tau+d\). On the other hand, the polynomial has at least \(q-\tau\) roots (on for each uncorrupted position of \(f\)). Hence, if \(q-\tau > \tau + d\), the polynomial is indeed the zero polynomial
End of Proof.