Computer Science/Discrete Mathematics Seminar I | |

Topic: | Lifting small locally testable codes (LTCs) to large LTCs via HDXs |

Speaker: | Prahladh Harsha |

Affiliation: | Tata Institute of Fundamental Research |

Date: | Monday, November 25 |

Time/Room: | 11:00am - 12:00pm/Simonyi Hall 101 |

Video Link: | https://video.ias.edu/csdm/2019/1125-PrahladhHarsha |

In this talk, I'll illustrate how to lift a "small" locally testable code via a high dimensional expander (HDX) to a "large" locally testable code. Given a D-left regular bipartite graph G = ([n], [m], E) and a "small" code C \in {0,1}^D, the Tanner construction shows how to lift this code to a "large" code on n- bits. These Tanner lifts are extremely useful. For instance, if C is a "small" code with good distance and rate and G is a bipartite expander, then the Sipser-Spielman analysis shows that the lifted code is a "large" code that has good distance and rate. We will show a similar lifting property for local-testability. More precisely, let C_0 be a small code such that its lift C (defined via a bipartite graph) has non-trivial rate. We will show that if the bipartite-graph is part of a HDX and a small-lift is testable, then so is the large-lift C.