<div dir="ltr"><div class="gmail_default" style="font-size:small">Forwarding information regarding the launch of a <font face="georgia, serif"><i>new, virtual </i></font><span style="font-family:arial,sans-serif">Theory Seminar Series called <b><i><font color="#0b5394">Algorithms and Theory at TTIC (ATTIC)</font></i></b> this week on 4/12:</span></div><div class="gmail_default" style="font-size:small"><br></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">---------- Forwarded message ---------<br>From: <strong class="gmail_sendername" dir="auto">Santhoshini Velusamy</strong> <span dir="auto"><<a href="mailto:santhoshini@ttic.edu" target="_blank">santhoshini@ttic.edu</a>></span><br>Date: Tue, Apr 9, 2024 at 11:28 AM<br>Subject: [TTIC Talks] Virtual theory seminar at TTIC<br>To: TTIC Talks <<a href="mailto:talks@ttic.edu" target="_blank">talks@ttic.edu</a>>,  <<a href="mailto:idealphase2@googlegroups.com" target="_blank">idealphase2@googlegroups.com</a>>,  <<a href="mailto:idealphase2-students@googlegroups.com" target="_blank">idealphase2-students@googlegroups.com</a>><br></div><br><br><div dir="ltr"><font face="arial, sans-serif">Hi everyone,</font><div><font face="arial, sans-serif"><br></font></div><div><font face="arial, sans-serif">We are kickstarting a <span class="gmail_default" style="font-size:small"></span>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 <a href="https://uchicago.zoom.us/j/92198136946?pwd=L3lkVWNxbU9vemMxOU96ZzFsbzhCdz09" target="_blank">this link</a> on <b>Friday, April 12 at 10 am CT</b>. Please feel free to share this email with anyone who might be interested.</font></div><div><font face="arial, sans-serif"><br></font></div><div><p style="margin:0px;font-stretch:normal;line-height:normal;font-size-adjust:none;font-kerning:auto;font-variant-alternates:normal;font-variant-ligatures:normal;font-variant-numeric:normal;font-variant-east-asian:normal;font-feature-settings:normal"><font face="arial, sans-serif">Title: An Exponential Lower Bound for Linear 3-Query Locally Correctable Codes</font></p><p style="margin:0px;font-stretch:normal;line-height:normal;font-size-adjust:none;font-kerning:auto;font-variant-alternates:normal;font-variant-ligatures:normal;font-variant-numeric:normal;font-variant-east-asian:normal;font-feature-settings:normal;min-height:14px"><font face="arial, sans-serif"><br></font></p><p style="margin:0px;font-stretch:normal;line-height:normal;font-size-adjust:none;font-kerning:auto;font-variant-alternates:normal;font-variant-ligatures:normal;font-variant-numeric:normal;font-variant-east-asian:normal;font-feature-settings:normal"><font face="arial, sans-serif">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.</font></p><p style="margin:0px;font-stretch:normal;line-height:normal;font-size-adjust:none;font-kerning:auto;font-variant-alternates:normal;font-variant-ligatures:normal;font-variant-numeric:normal;font-variant-east-asian:normal;font-feature-settings:normal;min-height:14px"><font face="arial, sans-serif"><br></font></p><p style="margin:0px;font-stretch:normal;line-height:normal;font-size-adjust:none;font-kerning:auto;font-variant-alternates:normal;font-variant-ligatures:normal;font-variant-numeric:normal;font-variant-east-asian:normal;font-feature-settings:normal"><font face="arial, sans-serif">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.</font></p><p style="margin:0px;font-stretch:normal;line-height:normal;font-size-adjust:none;font-kerning:auto;font-variant-alternates:normal;font-variant-ligatures:normal;font-variant-numeric:normal;font-variant-east-asian:normal;font-feature-settings:normal;min-height:14px"><font face="arial, sans-serif"><br></font></p><p style="margin:0px;font-stretch:normal;line-height:normal;font-size-adjust:none;font-kerning:auto;font-variant-alternates:normal;font-variant-ligatures:normal;font-variant-numeric:normal;font-variant-east-asian:normal;font-feature-settings:normal"><font face="arial, sans-serif">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.</font></p><p style="margin:0px;font-stretch:normal;line-height:normal;font-size-adjust:none;font-kerning:auto;font-variant-alternates:normal;font-variant-ligatures:normal;font-variant-numeric:normal;font-variant-east-asian:normal;font-feature-settings:normal;min-height:14px"><font face="arial, sans-serif"><br></font></p><p style="margin:0px;font-stretch:normal;line-height:normal;font-size-adjust:none;font-kerning:auto;font-variant-alternates:normal;font-variant-ligatures:normal;font-variant-numeric:normal;font-variant-east-asian:normal;font-feature-settings:normal"><span style="font-kerning:none"><font face="arial, sans-serif">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<span class="gmail_default" style="font-size:small"></span> was featured in Quanta magazine.</font></span></p></div><div><br></div><div>Regards,</div><div>Santhoshini</div><div><br></div></div>

</div></div>