News & Events

Theory of Computation Seminars

Lifting Small Locally Testable Codes (LTCs) to Large LTCs via High-Dimensional Expanders

Prahladh Harsha, Tata Institute of Fundamental Research

Monday, Feb 3, 2020

Expander graphs, over the last few decades, have played a pervasive role in almost all areas of theoretical computer science. Recently, various high-dimensional analogues of these objects have been studied in mathematics and even more recently, there have been some surprising applications in computer science, especially in the area of property testing, coding theory and approximate counting.

In this talk, I'll give a high-level introduction to these objects called high-dimensional expanders (HDXs). I'll then dwell into a particular application of HDXs towards construction of locally testable codes (LTCs): I will illustrate how to lift a ‘small’ locally testable code via a HDX expander to a ‘large’ locally testable code.  Given a D-left regular bipartite graph G = ([n], [m], E) and a ‘small’ code C {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, he will show that if C₀ is a base code, the bipartite-graph is part of an HDX and a small-lift is testable, then so is a large lift.

Speaker Bio

Prahladh Harsha is an Associate Professor at the School of Technology and Computer Science at the Tata Institute of Fundamental Research (TIFR), Mumbai, India. He obtained his BTech degree in Computer Science and Engineering from IIT Madras in 1998 and his PhD in Computer Science from the Massachusetts Institute of Technology (MIT) in 2004. He has worked at Microsoft Research, TTI Chicago and has been at TIFR since 2010. Prahladh's research interests are in the area of theoretical computer science, with special emphasis on computational complexity theory. He is best known for his work in the area of probabilistically checkable proofs.


Carol Harlow