<html><head><meta http-equiv="content-type" content="text/html; charset=us-ascii"></head><body dir="auto"><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><b><span style="font-size: 14pt; font-family: Helvetica;">Peter Manohar</span></b><o:p></o:p></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><b><span style="font-size: 14pt; font-family: Helvetica;">Institute for Advanced Study</span></b><o:p></o:p></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"> <o:p></o:p></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><span style="font-size: 11pt;"><img width="298" height="298" id="Picture_x0020_1" src="cid:A957DD9D-2E00-4DFD-BC79-07C469EE0FAD" alt="image001.png" style="width: 3.1041in; height: 3.1041in;"></span><span style="font-size: 11pt;"> </span><o:p></o:p></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><span style="font-size: 11pt;"> </span> <o:p></o:p></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><b><span style="font-size: 11pt;"><span dir="ltr">Tuesday, </span></span></b><b><span style="font-size: 11pt;"><span dir="ltr">February 11</span><span dir="ltr">, 202</span><span dir="ltr">5,</span><span dir="ltr"> at 3:30pm</span></span></b><o:p></o:p></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><b><span style="font-size: 11pt; background: yellow;">Kent Chemical Laboratory, Room 120</span></b><o:p></o:p></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><span style="font-size: 11pt;"> </span><o:p></o:p></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><span style="font-size: 11pt;"> </span><o:p></o:p></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><span style="font-size: 12pt;"> </span><o:p></o:p></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><b><i><span style="font-size: 12pt; color: rgb(33, 33, 33);">Title:</span></i></b><span style="font-size: 12pt; color: rgb(33, 33, 33);"> </span><span style="font-size: 12pt; color: rgb(33, 33, 33);">Lower Bounds for Locally Decodable and Correctable Codes from Induced Subgraphs of Cayley Graphs</span><o:p></o:p></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><span style="font-size: 12pt; color: rgb(33, 33, 33);"> </span><o:p></o:p></p><p style="-webkit-text-size-adjust: auto; margin: 0in;"><b><i><span style="color: rgb(33, 33, 33);">Abstract:</span></i></b><span style="color: rgb(33, 33, 33);"> </span><span style="color: rgb(33, 33, 33);">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).<o:p></o:p></span></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><span style="font-size: 12pt; font-family: Aptos, sans-serif; color: rgb(33, 33, 33);"> </span></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><span style="font-size: 12pt; font-family: Aptos, sans-serif; color: rgb(33, 33, 33);">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:<o:p></o:p></span></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><span style="font-size: 12pt; font-family: Aptos, sans-serif; color: rgb(33, 33, 33);">(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<o:p></o:p></span></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><span style="font-size: 12pt; font-family: Aptos, sans-serif; color: rgb(33, 33, 33);">(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.<o:p></o:p></span></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><span style="font-size: 12pt; font-family: Aptos, sans-serif; color: rgb(33, 33, 33);"> </span></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><span style="font-size: 12pt; font-family: Aptos, sans-serif; color: rgb(33, 33, 33);">Based on joint work with Omar Alrabiah, Venkat Guruswami, Oliver Janzer, and Pravesh K. Kothari. </span></p><div dir="ltr"></div></body></html>