Dmitry Mineev: Combinatorics, Algebra, and Geometry of Locally Testable Codes
Bar-Ilan University,Tel Aviv
Abstract: Sometimes one wants more from a linear error-correcting code than good rate and good distance. One may also want to check whether a message looks valid by examining only a tiny random portion of it. Properly formalized, this is called local testability. Many otherwise excellent codes, including ordinary random or expander LDPC codes, are not locally testable. This is bad news for naive constructions, but good news for mathematics: local testability seems to require a carefully curated balance of order and chaos, rather than pure randomness.
