As mentioned earlier, the study of LTCs arose naturally in works on program checking and PCPs. The Hadamard code was the first code proven to be locally testable in the work of Blum, Luby, and Rubinfeld on linearity testing [1]}. The low (logarithmic) rate of this code was quickly improved to polynomial rate by moving from linear functions (codewords of the Hadamard code) to low degree polynomial functions (codewords of the Reed Muller code). Subsequent works studied “low degree tests” which are in fact proofs that the Reed-Muller code is locally testable. These works were crucial for progress leading up to the proof of the PCP theorem. More on the relation between PCPs and LTCs, as well as the historical development, can be found in Goldreich's survey [2]}.
