(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.