Computer Science/Discrete Mathematics Seminar I
Lifting small locally testable codes (LTCs) to large LTCs via HDXs
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.