ICTS:31735

Video URL

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

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

(2025). Locally Testable Codes with the Multiplication Property from High-dimensional Expanders. SciVideos. https://youtube.com/live/nVJB9D0xSbA

Locally Testable Codes with the Multiplication Property from High-dimensional Expanders. SciVideos, May. 07, 2025, https://youtube.com/live/nVJB9D0xSbA 

          @misc{ scivideos_ICTS:31735,
            doi = {},
            url = {https://youtube.com/live/nVJB9D0xSbA},
            author = {},
            keywords = {},
            language = {en},
            title = {Locally Testable Codes with the Multiplication Property from High-dimensional Expanders},
            publisher = {},
            year = {2025},
            month = {may},
            note = {ICTS:31735 see, \url{https://scivideos.org/icts-tifr/31735}}
          }
Siqi Liu
Talk numberICTS:31735
Source RepositoryICTS-TIFR

Abstract

Expanders are well-connected graphs that have been extensively studied and have numerous applications in computer science, including error-correcting codes. High-dimensional expanders (HDXs) generalize expanders to hypergraphs and have the powerful local-to-global property. Roughly speaking, this property states that the expansion of an HDX can be certified by the expansion of certain local structures. This property has made HDXs crucial in the recent breakthrough on locally testable codes (LTCs) [Dinur et al.'22]. These LTCs simultaneously achieve constant rate, constant relative distance, and constant query complexity. However, despite these desirable properties, these LTCs have yet to find applications in proof systems, as they lack the crucial multiplication property present in widely used polynomial codes. A major open question is: Do there exist LTCs with the multiplication property that achieve the same rate, distance, and query complexity as those constructed by Dinur et al.?

In this talk, I will provide intuition behind the connection between HDXs and LTCs, explain why the LTCs by Dinur et al. lack the multiplication property, and discuss my recent and ongoing work on constructing LTCs with the multiplication property. This talk is based on joint work with Irit Dinur, Huy Tuan Pham, and Rachel Zhang.