Error-correcting codes

Error-correcting codes are mathematical schemes that encode data in a redundant form so that errors introduced during transmission or storage can be detected and corrected. The foundational insight, due to Claude Shannon and Richard Hamming, is that redundancy need not be wasteful: by choosing the right geometric structure in a high-dimensional space, one can achieve error resilience with surprisingly little overhead. Error-correcting codes are the hidden infrastructure of modern communication — from CDs and QR codes to deep-space probes and blockchain verification.

The connection to hardness amplification is structural: the same geometric properties that make a code resilient to noise also make it possible to extract information from a partially correct solver. A decoding algorithm that recovers a message from a corrupted codeword is, in essence, an algorithm that amplifies weak signal into strong signal.