Talks
Spring 2017

Expander-Based Constructions of Locally Testable and Locally Decodable Codes

Thursday, February 2nd, 2017, 2:55 pm3:40 pm

Add to Calendar

Location: 

Calvin Lab Auditorium

Locally testable and locally decodable codes are special families of error-correcting codes that admit highly efficient algorithms that detect and correct errors in transmission in sublinear time, probing only a small number of entries of the corrupted codeword. In recent years, there have been new developments on the construction of locally testable and locally decodable codes using graph-based/combinatorial constructions that exploit the power of expander graphs. These eventually led to the construction of asymptotically good locally testable and locally decodable codes with small (sub-polynomial) query complexity, and with near-optimal error-correction capabilities (approaching the Singleton and Gilbert-Varshamov bounds). In this talk I will survey some of these constructions and highlight the role of expander graphs in their development.