<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=utf-8">
<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;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
font-size:10.0pt;
font-family:"Calibri",sans-serif;}
p.p1, li.p1, div.p1
{mso-style-name:p1;
margin:0in;
font-size:8.5pt;
font-family:Helvetica;
color:#FF9400;}
span.EmailStyle19
{mso-style-type:personal-reply;
font-family:"Calibri",sans-serif;
color:windowtext;}
.MsoChpDefault
{mso-style-type:export-only;
font-size:10.0pt;}
@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="#0563C1" vlink="#954F72" style="word-wrap:break-word">
<div class="WordSection1">
<div>
<div>
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Arial",sans-serif"> </span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Arial",sans-serif"> </span><o:p></o:p></p>
</div>
</div>
</div>
<p class="p1"><i><span style="font-size:12.0pt;color:windowtext"> </span></i><o:p></o:p></p>
<p class="p1"><i><span style="font-size:12.0pt;color:#C00000">UNIVERSITY OF CHICAGO</span></i><o:p></o:p></p>
<p class="p1"><i><span style="font-size:12.0pt;color:#C00000">COMPUTER SCIENCE DEPARTMENT</span></i><o:p></o:p></p>
<p class="p1"><i><span style="font-size:12.0pt;color:#C00000">PRESENTS</span></i><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><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:12.0pt;font-family:Helvetica">Anup Rao</span></b><o:p></o:p></p>
<p class="MsoNormal"><b><span style="font-size:11.0pt;font-family:Helvetica">University of Washington</span></b><o:p></o:p></p>
<p class="MsoNormal"><b><span style="font-size:11.0pt;font-family:Helvetica"> </span></b><o:p></o:p></p>
<p class="MsoNormal"> <img width="204" height="168" style="width:2.125in;height:1.75in" id="_x0000_i1026" src="cid:image001.jpg@01D85FC7.EDDC5480" alt="A picture containing person, person, indoor, male
Description automatically generated"><o:p></o:p></p>
<p class="MsoNormal"><b><span style="font-size:11.0pt;font-family:Helvetica"> </span></b><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">Tuesday, May 31, 2022 at 3:30pm</span></b><o:p></o:p></p>
<p class="MsoNormal"><b><span style="font-size:11.0pt;background:yellow;mso-highlight:yellow">John Crerar Library, Room 298</span></b><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt"> </span><o:p></o:p></p>
<p class="MsoNormal" align="center" style="text-align:center;background:white"><b><span style="font-size:14.0pt;font-family:"Arial",sans-serif;color:black"> </span></b><o:p></o:p></p>
<p class="MsoNormal" style="margin-bottom:8.0pt;line-height:11.75pt"><b><span style="font-size:11.0pt;font-family:"Arial",sans-serif;color:black">“</span></b><b><span style="font-size:11.0pt;font-family:"Arial",sans-serif">A Fourier Analytic Criterion for Decoding
on the BSC<span style="color:black">”</span></span></b><o:p></o:p></p>
<p class="MsoNormal" style="margin-bottom:8.0pt;line-height:11.75pt"><span style="font-size:11.0pt"> </span><o:p></o:p></p>
<p class="MsoNormal" style="margin-bottom:8.0pt;line-height:11.75pt"><span style="font-size:11.0pt;font-family:"Arial",sans-serif;color:black"> <b>Abstract:</b></span><span style="font-size:11.0pt;font-family:"Arial",sans-serif">
</span><span style="font-size:12.0pt">We present an approach to showing that a linear code is resilient to random errors. We then use this approach to obtain decoding results for both transitive codes and Reed-Muller codes. We give three kinds of results about
linear codes in general, and transitive linear codes in particular.</span><o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="font-size:12.0pt;color:black">1. We give a tight bound on the weight distribution of every transitive linear code C </span><span style="font-size:12.0pt;font-family:"Cambria Math",serif;color:black">⊆</span><span style="font-size:12.0pt;color:black"> F<span style="position:relative;top:-4.0pt;mso-text-raise:4.0pt">N</span><span style="position:relative;top:3.0pt;mso-text-raise:-3.0pt">2 </span>:
Pr<span style="position:relative;top:2.0pt;mso-text-raise:-2.0pt">c</span></span><span style="font-size:12.0pt;font-family:"Cambria Math",serif;color:black;position:relative;top:2.0pt;mso-text-raise:-2.0pt">∈</span><span style="font-size:12.0pt;color:black;position:relative;top:2.0pt;mso-text-raise:-2.0pt">C</span><span style="font-size:12.0pt;color:black">[|c| = αN] ≤ 2<span style="position:relative;top:-4.0pt;mso-text-raise:4.0pt">−(1−h(α))·dim(C)</span>. </span><o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="font-size:12.0pt;color:black">2. We give a Fourier analytic criterion that certifies that a linear code C can be decoded on the binary symmetric channel. Let L<span style="position:relative;top:2.0pt;mso-text-raise:-2.0pt">w</span>(x)
denote the level function that is 1 if |x| = w and 0 otherwise, and let C</span><span style="font-size:12.0pt;font-family:"Cambria Math",serif;color:black;position:relative;top:-4.0pt;mso-text-raise:4.0pt">⊥</span><span style="font-size:12.0pt;color:black;position:relative;top:-4.0pt;mso-text-raise:4.0pt"> </span><span style="font-size:12.0pt;color:black">denote
the dual code of C. We show that bounds on <span style="position:relative;top:1.0pt;mso-text-raise:-1.0pt">E</span><span style="position:relative;top:3.0pt;mso-text-raise:-3.0pt">c</span></span><span style="font-size:12.0pt;font-family:"Cambria Math",serif;color:black;position:relative;top:3.0pt;mso-text-raise:-3.0pt">∈</span><span style="font-size:12.0pt;color:black;position:relative;top:3.0pt;mso-text-raise:-3.0pt">C</span><span style="font-size:12.0pt;font-family:"Cambria Math",serif;color:black">⊥</span><span style="font-size:12.0pt;color:black">[L<span style="position:relative;top:-3.0pt;mso-text-raise:3.0pt">ˆ</span><span style="position:relative;top:2.0pt;mso-text-raise:-2.0pt">εN</span>(c)<span style="position:relative;top:-4.0pt;mso-text-raise:4.0pt">2</span>]
imply that C recovers from errors on the binary symmetric channel with parameter ε. Weaker bounds can be used to obtain list-decoding results using similar methods. </span><o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="font-size:12.0pt;color:black">3. Motivated by the above results, we use complex analysis to give tight estimates for the Fourier coefficients of the level function.
We then combine these estimates with our weight distribution bound to give list-decoding results for transitive linear codes and Reed-Muller codes. </span><o:p></o:p></p>
<p class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto"><span style="font-size:12.0pt;color:black">Joint work with Oscar Sprumont.</span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:12.0pt;font-family:"Times New Roman",serif"> </span><o:p></o:p></p>
<p class="MsoNormal"><i><span style="font-size:12.0pt;color:black">Bio:</span></i><span style="font-size:12.0pt;color:black"> Anup Rao is a professor of computer science at the Paul G. Allen School of Computing at the University of Washington. </span><o:p></o:p></p>
<p class="MsoNormal" style="margin-bottom:8.0pt;mso-line-height-alt:11.75pt"><span style="font-size:12.0pt"> </span><o:p></o:p></p>
<p class="MsoNormal" style="margin-bottom:8.0pt;line-height:11.75pt"><span style="font-size:11.0pt;font-family:"Arial",sans-serif;color:black"> </span><o:p></o:p></p>
<div>
<div>
<p class="MsoNormal"><b><span style="font-size:12.0pt;font-family:Helvetica">Host:
</span></b><b><span style="font-size:14.0pt">Aaron Potechin</span></b><o:p></o:p></p>
<p class="MsoNormal"><b><span style="font-size:12.0pt;font-family:Helvetica"> </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:11.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;font-family:"Arial",sans-serif">Jose J Fragoso</span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Arial",sans-serif">Project Assistant IV</span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Arial",sans-serif">Computer Science Department</span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Arial",sans-serif">5730 S. Ellis – Room 200C</span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Arial",sans-serif">Chicago, IL. 60637</span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Arial",sans-serif">jfragoso@uchicago.edu</span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Arial",sans-serif">(773) 702-6614</span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Arial",sans-serif">(773) 702-8487 FAX</span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Arial",sans-serif"> </span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Arial",sans-serif"><img width="92" height="92" style="width:.9583in;height:.9583in" id="Picture_x0020_1" src="cid:image003.png@01D83D68.0E6B3630" alt="signature_1572818061"></span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Arial",sans-serif"> </span><o:p></o:p></p>
</div>
</div>
<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><o:p></o:p></p>
</div>
</body>
</html>