Locally Testable Codes with the Multiplication Property from High-dimensional Expanders

This Computer Science/Discrete Mathematics Seminar explores the construction of Locally Testable Codes (LTCs) with the multiplication property using high-dimensional expanders. Learn about error-correcting codes that can be verified by querying only a small number of positions, with rejection probability proportional to the distance from the code. Discover how recent work has led to LTCs with optimal rate, distance, and query complexity, but which lack the crucial multiplication property found in polynomial codes used in proof systems. Follow Siqi Liu from the Institute for Advanced Study as he discusses the connection between high-dimensional expanders and LTCs, presenting his joint research with Irit Dinur, Rachel Yun Zhang, and Huy Tuan Pham that aims to construct LTCs with the multiplication property while maintaining optimal parameters.