[Theory] UC Theory Seminar

[Alexander Razborov via Theory]

Peter Manohar
Institute for Advanced Study
 
 
  
Tuesday, February 11, 2025, at 3:30pm
Kent Chemical Laboratory, Room 120
 
 
 
Title: Lower Bounds for Locally Decodable and Correctable Codes from Induced Subgraphs of Cayley Graphs
 
Abstract: An error-correcting code is locally decodable (LDC) if one can recover any symbol of the original message by querying only a small number of randomly chosen symbols from the received corrupted codeword. The definition of a locally correctable code (LCC) is similar; one must additionally be able to recover any symbol of the original uncorrupted codeword. Despite over two decades of research, our understanding of the optimal length of an LDC/LCC, as a function of k, the message length, and q, the number of queries, remains quite limited. The best constructions have length n = 2^{k^{1/q}} for q-query LCCs and n = 2^{k^{o(1)}} for q-query LDCs, while the best lower bounds on n are small polynomials in k. In particular, for 3-query LDCs/LCCs, the best lower bound remains the quadratic n > k^2 lower bound of Kerenidis and de Wolf (2004).
 
In this talk, we will discuss a new approach to proving lower bounds for LDCs/LCCs using spectral properties of certain induced subgraphs of Cayley graphs called Kikuchi graphs. Using this method, we obtain:
(1) A k^3 lower bound for 3-query LDCs, and more generally a polynomial improvement in the lower bounds for odd-query locally decodable codes, and
(2) An exponential lower bound for 3-query locally correctable codes, showing that Reed--Muller codes are near-optimal 3-query LCCs and that the best 3-query LDCs are not locally correctable.
 
Based on joint work with Omar Alrabiah, Venkat Guruswami, Oliver Janzer, and Pravesh K. Kothari. 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20250204/65dddc63/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image001.png
Type: image/png
Size: 279705 bytes
Desc: not available
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20250204/65dddc63/attachment-0001.png>