Computer Science/Discrete Mathematics Seminar II

We show that random sparse binary linear codes are locally testable and locally decodable (under any linear encoding) with constant queries (with probability tending to one). By sparse, we mean that the code should have only polynomially many codewords. Our results are the first to show that local decodability and testability can be found in random, {em unstructured}, codes. Previously known locally decodable or testable codes were either classical algebraic codes, or new ones constructed very carefully. Joint work with Madhu Sudan (MIT)