2021 Croucher Summer Course in Information Theory, The Chinese University of Hong Kong
Locally-testable and locally-decodable codes are special families of error-correcting codes that admit highly efficient algorithms that detect and correct errors in transmission in sublinear time, probing only a small number of entries of the corrupted codeword. These codes have arisen from a variety of motivations within the theory of computation, and the study of these codes had a significant effect on coding theory as well. In this talk we will survey the motivations for the study of locally-testable and locally-decodable codes within the theory of computation and some of the state-of-the-art results. We will also highlight some of the most interesting challenges that remain.