<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=us-ascii">
<meta name="Generator" content="Microsoft Word 15 (filtered medium)">
<!--[if !mso]><style>v\:* {behavior:url(#default#VML);}
o\:* {behavior:url(#default#VML);}
w\:* {behavior:url(#default#VML);}
.shape {behavior:url(#default#VML);}
</style><![endif]--><style><!--
/* Font Definitions */
@font-face
{font-family:Helvetica;
panose-1:0 0 0 0 0 0 0 0 0 0;}
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
@font-face
{font-family:Aptos;
panose-1:2 11 0 4 2 2 2 2 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
font-size:10.0pt;
font-family:"Calibri",sans-serif;}
span.apple-converted-space
{mso-style-name:apple-converted-space;}
.MsoChpDefault
{mso-style-type:export-only;
font-size:10.0pt;
mso-ligatures:none;}
@page WordSection1
{size:8.5in 11.0in;
margin:1.0in 1.0in 1.0in 1.0in;}
div.WordSection1
{page:WordSection1;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]-->
</head>
<body lang="EN-US" link="blue" vlink="purple" style="word-wrap:break-word">
<div class="WordSection1">
<div id="mail-editor-reference-message-container">
<div>
<div>
<div>
<div id="mail-editor-reference-message-container">
<div>
<div>
<div>
<div id="mail-editor-reference-message-container">
<div>
<div>
<div>
<div id="mail-editor-reference-message-container">
<div>
<div>
<div>
<div id="mail-editor-reference-message-container">
<div>
<div>
<div>
<div>
<div id="mail-editor-reference-message-container">
<div>
<div>
<div>
<div id="mail-editor-reference-message-container">
<div>
<div>
<div>
<div id="mail-editor-reference-message-container">
<div>
<div>
<div>
<div id="mail-editor-reference-message-container">
<div>
<div>
<div>
<div id="mail-editor-reference-message-container">
<div>
<div>
<div>
<div id="mail-editor-reference-message-container">
<div>
<div>
<div>
<div id="mail-editor-reference-message-container">
<div>
<div>
<div>
<div>
<div id="mail-editor-reference-message-container">
<div>
<div>
<div>
<div id="mail-editor-reference-message-container">
<div>
<div>
<div id="mail-editor-reference-message-container">
<div>
<div>
<div id="mail-editor-reference-message-container">
<div>
<div>
<div>
<div id="mail-editor-reference-message-container">
<div>
<div>
<div>
<div id="mail-editor-reference-message-container">
<div>
<div>
<div>
<div id="mail-editor-reference-message-container">
<div>
<div>
<div>
<div id="mail-editor-reference-message-container">
<div>
<div>
<div>
<div id="mail-editor-reference-message-container">
<div>
<div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Aptos",sans-serif"> </span><i><span style="font-size:12.0pt;font-family:Helvetica;color:#8B0102"> </span></i><o:p></o:p></p>
<p class="MsoNormal"> <o:p></o:p></p>
<p class="MsoNormal"><i><span style="font-size:12.0pt;font-family:Helvetica;color:#8B0102">UNIVERSITY OF CHICAGO</span></i><o:p></o:p></p>
<p class="MsoNormal"><i><span style="font-size:12.0pt;font-family:Helvetica;color:#8B0102">COMPUTER SCIENCE DEPARTMENT</span></i><o:p></o:p></p>
<p class="MsoNormal"><i><span style="font-size:12.0pt;font-family:Helvetica;color:#8B0102">PRESENTS</span></i><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:black"> </span><o:p></o:p></p>
<p class="MsoNormal"> <o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:black"> </span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:black"> </span><o:p></o:p></p>
<p class="MsoNormal"><b><span style="font-size:14.0pt;font-family:Helvetica">Peter Manohar</span></b><o:p></o:p></p>
<p class="MsoNormal"><b><span style="font-size:14.0pt;font-family:Helvetica">Institute for Advanced Study</span></b><o:p></o:p></p>
<p class="MsoNormal"> <o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt"><img width="298" height="298" style="width:3.1041in;height:3.1041in" id="Picture_x0020_1" src="cid:image001.png@01DB73E6.121FD530"> </span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt"> </span> <o:p></o:p></p>
<p class="MsoNormal"><b><span style="font-size:11.0pt;color:black">Tuesday, </span>
</b><b><span style="font-size:11.0pt">February 11<span style="color:black">, 202</span>5,<span style="color:black"> at 3:30pm</span></span></b><o:p></o:p></p>
<p class="MsoNormal"><b><span style="font-size:11.0pt;color:black;background:yellow">Kent Chemical Laboratory, Room 120</span></b><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:black"> </span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt"> </span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:12.0pt"> </span><o:p></o:p></p>
<p class="MsoNormal"><b><i><span style="font-size:12.0pt;color:#212121">Title:</span></i></b><span style="font-size:12.0pt;color:#212121"> Lower Bounds for Locally Decodable and Correctable Codes from Induced Subgraphs of Cayley Graphs</span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:12.0pt;color:#212121"> </span><o:p></o:p></p>
<p style="margin:0in"><b><i><span style="color:#212121">Abstract:</span></i></b><span style="color:#212121"> 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).</span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:12.0pt;font-family:"Aptos",sans-serif;color:#212121"> </span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:12.0pt;font-family:"Aptos",sans-serif;color:#212121">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:</span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:12.0pt;font-family:"Aptos",sans-serif;color:#212121">(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</span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:12.0pt;font-family:"Aptos",sans-serif;color:#212121">(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.</span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:12.0pt;font-family:"Aptos",sans-serif;color:#212121"> </span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:12.0pt;font-family:"Aptos",sans-serif;color:#212121">Based on joint work with Omar Alrabiah, Venkat Guruswami, Oliver Janzer, and Pravesh K. Kothari. </span><o:p></o:p></p>
<p class="MsoNormal"> <o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:12.0pt;color:#212121"> </span><o:p></o:p></p>
<p style="margin:0in"><b><i><span style="color:#212121">Bio:</span></i></b><span style="color:#212121"> 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.</span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:12.0pt;font-family:"Aptos",sans-serif"> </span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:12.0pt"> </span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt"> </span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt"> </span><span style="font-size:12.0pt"> </span><o:p></o:p></p>
<p class="MsoNormal"> <span style="font-size:11.0pt"> </span><o:p></o:p></p>
<p style="margin-bottom:12.0pt"><b><span style="font-family:Helvetica;color:black">Host:<span class="apple-converted-space"> A</span></span></b><span class="apple-converted-space"><b><span style="font-family:Helvetica">aron Potechin</span></b></span><o:p></o:p></p>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</body>
</html>