
Locally Testable Codes with the Multiplication Property from High-dimensional Expanders
Siqi Liu, of the Institute for Advanced Study, presents research on locally testable codes, error-correcting codes whose validity can be checked by querying only a few positions. She reviews classic examples like Hadamard and Reed-Muller codes and explains how recent work (DELLM'22) used high-dimensional expander-like objects to build LTCs with optimal rate, distance, and query complexity. The catch is that these new codes lack the multiplication property that polynomial codes have, a property essential for use in proof systems. Liu discusses her ongoing work, joint with Irit Dinur, Rachel Yun Zhang, and Huy Tuan Pham, attempting to construct LTCs that combine both the multiplication property and the strong parameters of the expander-based constructions. The talk is a research seminar aimed at specialists, tracing the open problem from its origins through current partial results and remaining obstacles in combining coding theory with high-dimensional expansion.