<div dir="ltr"><div class="gmail_default" style=""><div class="gmail_default" style=""><p style="font-size:small;font-variant-numeric:normal;font-variant-east-asian:normal;font-stretch:normal;line-height:normal;color:rgb(80,0,80);margin:0px"><font face="arial, sans-serif" color="#000000"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><b>When:</b>    </font></font><font style="vertical-align:inherit"><font style="vertical-align:inherit">  Monday, January 10th at<b> <span style="background-color:rgb(255,255,255)">11:00 am CT</span></b></font></font><br></font></p><p class="MsoNormal" style="font-size:small;margin:0in 0in 0.0001pt;color:rgb(80,0,80);line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif" color="#000000"> </font></p><p class="MsoNormal" style="font-size:small;margin:0in 0in 0.0001pt;color:rgb(80,0,80);line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><font style="color:rgb(0,0,0);vertical-align:inherit"><font style="vertical-align:inherit"><b>Where:</b>     </font></font><font color="#000000">Zoom Virtual Talk (</font><font color="#0000ff"><b><a href="https://uchicagogroup.zoom.us/webinar/register/WN_HmAUeR9XSMubFowpjq2DzA" target="_blank">register in advance here</a></b></font><font color="#000000">)</font></font></p><p class="MsoNormal" style="font-size:small;margin:0in 0in 0.0001pt;color:rgb(80,0,80);line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><br></p><p class="MsoNormal" style="font-size:small;margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><font color="#000000"><b>Who: </b> </font><font color="#500050">    </font><font color="#000000">  </font></font></font></font>Ray Li, Stanford University</p><p class="MsoNormal" style="font-size:small;margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><br></p><p class="MsoNormal" style="font-size:small;margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><b><br></b></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif" style=""><b style="">Title:</b>        <span style="color:rgb(0,0,0)">Two Stories in Coding Theory</span>      </font></p><div style=""><font face="arial, sans-serif"><br></font></div><div style=""><b><font face="arial, sans-serif">Abstract:</font></b></div><div style=""><p class="MsoNormal" style="margin:0in;line-height:12pt;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><span style="color:black"><font face="arial, sans-serif" style="">Error-correcting codes protect information from noise. In the
standard setup, a sender, Alice, wants to send a message <span style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial">through a noisy channel</span> to a receiver,
Bob. To protect the message from noise, Alice encodes the message with an
error-correcting code so that Bob can recover the message even in the presence
of noise. I will talk about fundamental challenges in two basic coding theory
contexts: deletion codes and list-decoding.</font></span></p>

<p class="MsoNormal" style="margin:0in;line-height:12pt;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><span style="color:black"><font face="arial, sans-serif"> </font></span></p>

<p class="MsoNormal" style="margin:0in;line-height:12pt;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><span style="color:black"><font face="arial, sans-serif">In deletion codes (Levenshtein '66, Ullman '67), the noisy channel
transmits a subsequence of Alice's encoded message. Though deletion codes is an
old topic, our understanding was poor <span style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial">compared
to other errors like bit-flips and erasures, and many basic questions remained
open until recently</span>. I will talk about some of this recent
progress, focusing on work that answers one extremely basic question: can
positive rate binary codes correct a worst-case deletion fraction approaching
the natural limit of 1/2?</font></span></p>

<p class="MsoNormal" style="margin:0in;line-height:12pt;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><span style="color:black"><font face="arial, sans-serif"> </font></span></p>

<p class="MsoNormal" style="line-height:12pt;margin:0in 0in 8pt"><span style="color:black;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif" style="">In list decoding (Elias '57, Wozencraft '58), Bob only needs
to output a small list of messages containing the correct message. This
relaxation allows the protocol to tolerate more noise (approximately twice as
much). For this reason (and others), list-decoding finds various applications
such as communications, group testing, compressed sensing, pseudorandomness,
complexity, and cryptography. All applications require explicit list-decodable
codes, but our best list-decodable codes are often non explicit random codes.
Towards finding optimal explicit list-decodable codes, I will talk about recent
progress studying more-structured ensembles of codes, such as random linear
codes and random Reed Solomon codes.</font></span></p></div></div><div class="gmail_default" style=""><span style="color:rgb(17,17,17)"><font face="arial, sans-serif"><br></font></span></div><div class="gmail_default" style=""><font face="arial, sans-serif"><span style="color:rgb(17,17,17)"><b>Host</b>: </span><a href="mailto:madhurt@ttic.edu" target="_blank" style=""><b>Madhur Tulsiani</b></a></font></div><div class="gmail_default" style=""><font face="arial, sans-serif"><br></font></div></div><div><div dir="ltr" class="gmail_signature" data-smartmail="gmail_signature"><div dir="ltr"><div><span style="font-family:arial,helvetica,sans-serif;font-size:x-small"><br></span></div><div><span style="font-family:arial,helvetica,sans-serif;font-size:x-small"><br></span></div><div><span style="font-family:arial,helvetica,sans-serif;font-size:x-small">Mary C. Marre</span><br></div><div><div><font face="arial, helvetica, sans-serif" size="1">Faculty Administrative Support</font></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6" size="1"><b>Toyota Technological Institute</b></font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6" size="1">6045 S. Kenwood Avenue</font></i></div><div><font size="1"><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Chicago, IL  60637</font></i><br></font></div><div><b><i><a href="mailto:mmarre@ttic.edu" target="_blank"><font face="arial, helvetica, sans-serif" size="1">mmarre@ttic.edu</font></a></i></b></div></div></div></div></div></div>