Locally Testable Codes with the Multiplication Property from High-dimensional Expanders - Siqi Liu скачать в хорошем качестве

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

Computer Science/Discrete Mathematics Seminar II 10:30am|Simonyi 101 and Remote Access Topic: Locally Testable Codes with the Multiplication Property from High-dimensional Expanders Speaker: Siqi Liu Affiliation: Institute for Advanced Study Date: April 1, 2025 A locally testable code (LTC) is an error-correcting code equipped with a tester T that, given an input string x, queries only a small number of positions and rejects x with probability proportional to its distance from the code. Classic examples of LTCs include Hadamard codes and Reed-Muller codes, which have played fundamental roles in the construction of many proof systems. Recent work [DELLM'22] has led to the construction of LTCs with asymptotically optimal rate, distance, and query complexity using high-dimensional expander-like objects. However, despite these strong properties, these new LTCs have yet to be applied in proof systems, as they lack the crucial multiplication property present in widely used polynomial codes. This raises a major open question: Can we construct LTCs with the multiplication property that match the rate, distance, and query complexity of those in [DELLM'22]? In this talk, I will explore the connection between high-dimensional expanders and LTCs and discuss my recent and ongoing efforts to construct LTCs with the multiplication property from high-dimensional expanders. This is based on joint work with Irit Dinur, Rachel Yun Zhang, and Huy Tuan Pham.