Computer Science/Discrete Mathematics Seminar II

A locally decodable code (LDC) is an error correcting code that allows for probabilistic decoding of a single message bit by reading a corrupted encoding in a small number of locations. Until recently, the only LDC constructions known where based on low degree polynomial codes (Reed Muller) where the decoding is done by restrictions to random lines. In a breakthrough result three years ago, Yekhanin [Yek07] showed a new family of LDC's based on families of vectors with restricted dot-products (Matching vectors). These codes were developed further by Efremenko [Efr09] which gave the first sub-exponential codes with constant locality. In a recent joint work with Gopalan and Yekhanin [DGY10] we showed that these codes can be viewed as variants of polynomial codes and gave an improved decoding algorithm based on this view. In this talk I plan to show the construction of these codes from scratch (or almost from scratch) together with the improved decoding algorithm from [DGY10].