Sparse Random Linear Codes are Locally Decodable and Testable

COMPUTER SCIENCE DISCRETE MATH II
Topic:Sparse Random Linear Codes are Locally Decodable and Testable
Speaker:Tali Kaufman
Affiliation:Member and School of Mathematics
Date:Tuesday, October 16
Time/Room:10:30am - 12:30pm/S-101

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)