Alladi Ramakrishnan Hall

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

Venkatesan Guruswami

University of California, Berkeley

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.