Expander-Based Constructions of Locally Testable and Locally Decodable Codes

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. In recent years, there have been new developments on the construction of locally testable and locally decodable codes using graph-based/combinatorial constructions that exploit the power of expander graphs. These eventually led to the construction of asymptotically good locally testable and locally decodable codes with small (sub-polynomial) query complexity, and with near-optimal error-correction capabilities (approaching the Singleton and Gilbert-Varshamov bounds). In this talk I will survey some of these constructions and highlight the role of expander graphs in their development.