题目：A near-cubic lower bound for 3-query locally decodable codes

主讲人：Venkatesan Guruswami 教授 卡内基梅隆大学

邀请人：邢朝平教授 网络空间安全学院

时间：2022年11月10日上午9:30-10:30

Zoom会议号: 934 9903 9504    密码: 311298

Abstract:
Locally decodable codes (LDCs) allow for ultra-efficient recovery of any single message symbol by querying very few symbols of the associated codeword, even in the presence of a constant fraction of errors. In addition to their appeal for storage and cryptographic applications, locality as a concept drives many connections between coding theory and computational complexity.
An outstanding challenge concerning LDCs is their optimal encoding length for a desired number q of queries. For q=2, it is known that exponential blow-up in encoding length is necessary (and the simple Hadamard code achieves this). For q > 2, however, there are significant gaps in our understanding. For instance, for 3-query LDCs, the best known constructions have sub-exponential encoding length, whereas the best known lower bound, that has stood for two decades, was only quadratic.
In this talk, we will describe a near-cubic lower bound on the encoding length of 3-query LDCs. The approach is inspired by and borrows from recent advances in refuting semi-random instances of constraint satisfaction problems.
Joint work with Omar Alrabiah, Pravesh Kothari, and Peter Manohar.