[Colloquium] CS Theory Seminar - Tuesday, February 11, 2025

[Jose J Fragoso via Colloquium]

UNIVERSITY OF CHICAGO
COMPUTER SCIENCE DEPARTMENT
PRESENTS




Peter Manohar
Institute for Advanced Study

[cid:image001.png at 01DB73E6.121FD530]

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.



Bio: Peter is a postdoctoral researcher at the Institute for Advanced Study. He received his PhD in Computer Science from Carnegie Mellon University in 2024, advised by Venkatesan Guruswami and Pravesh Kothari, and his B.S. in EECS from UC Berkeley in 2019. His research interests span several areas of theoretical computer science, including spectral algorithms, coding theory, and extremal combinatorics.






Host: Aaron Potechin
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20250211/61b13b25/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image001.png
Type: image/png
Size: 279705 bytes
Desc: image001.png
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20250211/61b13b25/attachment-0001.png>