[Theory] Fwd: [TTIC Talks] Virtual theory seminar at TTIC

[Mary Marre]

Forwarding information regarding the launch of a *new, virtual *Theory
Seminar Series called *Algorithms and Theory at TTIC (ATTIC)* this week on
4/12:


---------- Forwarded message ---------
From: Santhoshini Velusamy <santhoshini at ttic.edu>
Date: Tue, Apr 9, 2024 at 11:28 AM
Subject: [TTIC Talks] Virtual theory seminar at TTIC
To: TTIC Talks <talks at ttic.edu>, <idealphase2 at googlegroups.com>, <
idealphase2-students at googlegroups.com>


Hi everyone,

We are kickstarting a new virtual theory seminar series called Algorithms
and theory at TTIC (ATTIC) this week. Our first speaker is Peter Manohar
from Carnegie Mellon University who will talk about his recent breakthrough
result on locally correctable codes (more details below). The talk will
take place on zoom at this link
<https://uchicago.zoom.us/j/92198136946?pwd=L3lkVWNxbU9vemMxOU96ZzFsbzhCdz09>
on
*Friday, April 12 at 10 am CT*. Please feel free to share this email with
anyone who might be interested.

Title: An Exponential Lower Bound for Linear 3-Query Locally Correctable
Codes


Abstract: A locally correctable code (LCC) is an error correcting code
where one can recover any symbol of the original codeword by querying only
a small number of randomly chosen symbols from the received corrupted
codeword.


In this talk, we present a proof that the blocklength n of a linear 3-query
LCC C: {0,1}^k -> {0,1}^n must be at least \exp(k^{1/8}), i.e., it grows
exponentially with k. This improves on the prior best lower bound of k^3
shown in our recent work, which holds even for the weaker setting of
3-query locally decodable codes (LDCs), and comes close to matching the
best-known construction of 3-query LCCs based on Reed—Muller codes, which
achieve a blocklength of n = \exp(\sqrt{k}). Because there is a 3-query LDC
with a strictly subexponential blocklength, as a corollary we obtain the
first separation between q-query LCCs and LDCs for any constant q.


We subsequently show that any “design 3-LCC”, an LCC with a parity check
matrix that is a block design, must have blocklength at least 2^{(1-o(1))
sqrt{k}}. As Reed—Muller codes are design 3-LCCs with blocklength n = 2^{2
sqrt{2k}}, this is tight up to a factor of 2 sqrt{2} in the exponent, and
as a corollary resolves the Hamada conjecture for 4-designs up to this
constant factor. For nonlinear LCCs, we give a generalization of our
approach that proves a superpolynomial lower bound of k^{log k}, improving
on the prior best lower bound of k^3.


Bio: Peter Manohar is a fifth year PhD student at Carnegie Mellon
University, advised by Venkatesan Guruswami and Pravesh Kothari. He
received a B.S. in EECS from UC Berkeley in 2019, where he worked with
Alessandro Chiesa and Ren Ng. His research interests span several areas of
theoretical computer science, including algorithm design, coding theory,
and extremal combinatorics. His work on refutation algorithms for
semirandom and smoothed instances of constraint satisfaction problems was
chosen as an ACM SIGACT research highlight in 2022 and his recent work on
lower bounds for locally correctable codes was featured in Quanta magazine.

Regards,
Santhoshini
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20240409/45023d66/attachment.html>