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)