(This is a continuation of a previous post.)

The goal now is to find such an encoding/decoding. We reduce this problem further to the problem of finding an algorithm that adjusts a word in to a codeword (rather than a message) with nontrivial accuracy, and the reduction will be valid as long as we can efficiently translate between the messages and codewords. Formally,

**Definition 7**: A **local -correcting algorithm** for an encoding is a probabilistic algorithm that, given oracle access to a received word and an input position , computes with probability 2/3 the value for any codeword -close to . For coin tosses , the output of the algorithm will be denoted by , and probability is taken over all .

**Definition 8**: An encoding is **systematic** if there exists a “translation” map running in time polynomial in the length of the domain and a map such that for all messages and corresponding codewords , .

We can get a decoder by sending input position through such a translation map and then through a local corrector:

**Result 4**: If is a systematic encoding and the code has a local -correcting algorithm in time , then has a local -decoding algorithm running in time .

We will design a local corrector and system encoding for the Reed-Muller code. We then concatenate to the Hadamard code to obtain a binary alphabet, and this will turn out to give the desired hardness amplification.