Seminar • Algorithms and Complexity • An Exponential Lower Bound for 2-query Relaxed Locally Decodable Codes

Please note: This seminar will take place in DC 1302 and online.

Elena Grigorescu, Professor
David R. Cheriton School of Computer Science

Locally Decodable Codes (LDCs) are error-correcting codes with super-fast decoding algorithms. They are important mathematical objects in many areas of theoretical computer science, yet the best constructions so far have codeword length that is super-polynomial in the message length, for codes with constant query complexity and constant alphabet size.

In a very surprising result, Ben-Sasson, Goldreich, Harsha, Sudan, and Vadhan (SICOMP 2006) showed how to construct a relaxed version of LDCs (RLDCs) with constant query complexity and almost linear codeword length over the binary alphabet and used them to obtain significantly improved constructions of Probabilistically Checkable Proofs.

In this talk I will present an exponential lower bound on the length of RLDCs making 2 queries, over the binary alphabet. This answers a question explicitly raised by Gur and Lachish (SICOMP 2021) and is the first exponential lower bound for RLDCs. Combined with the results of Ben-Sasson et al., our result exhibits a “phase-transition”-type behavior on the codeword length for some constant query complexity.

Joint work with Alex Block, Jeremiah Blocki, Kuan Cheng, Xin Li, Yu Zheng, and Minshen Zhu (Appeared in CCC 2023).

To attend this seminar in person, please go to DC 1302. You can also attend virtually using Zoom.