<div dir="ltr"><div dir="ltr"><div class="gmail_default" style="font-size:small"><div class="gmail_default" style="color:rgb(80,0,80)"><p style="font-variant-numeric:normal;font-variant-east-asian:normal;font-stretch:normal;line-height:normal;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> 11:00 am CT</b></font></font><br></font></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" color="#000000"> </font></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"><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="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="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="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="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"><b>Title:</b> <span style="color:rgb(0,0,0)">Two Stories in Coding Theory</span> </font></p><div><font face="arial, sans-serif"><br></font></div><div><b><font face="arial, sans-serif">Abstract:</font></b></div><div><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">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="margin:0in 0in 8pt;line-height:12pt"><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">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="color:rgb(80,0,80)"><span style="color:rgb(17,17,17)"><font face="arial, sans-serif"><br></font></span></div><div class="gmail_default" style="color:rgb(80,0,80)"><font face="arial, sans-serif"><span style="color:rgb(17,17,17)"><b>Host</b>: </span><a href="mailto:madhurt@ttic.edu" target="_blank"><b>Madhur Tulsiani</b></a></font></div><div class="gmail_default" style="color:rgb(80,0,80)"><br></div><div class="gmail_default" style="color:rgb(80,0,80)"><br></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">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><br></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Mon, Jan 10, 2022 at 10:10 AM Mary Marre <<a href="mailto:mmarre@ttic.edu">mmarre@ttic.edu</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div dir="ltr"><div style="font-size:small"><div><p style="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> 11:00 am CT</b></font></font><br></font></p><p class="MsoNormal" style="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="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="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="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="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="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"><b>Title:</b> <span style="color:rgb(0,0,0)">Two Stories in Coding Theory</span> </font></p><div><font face="arial, sans-serif"><br></font></div><div><b><font face="arial, sans-serif">Abstract:</font></b></div><div><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">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="margin:0in 0in 8pt;line-height:12pt"><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">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><span style="color:rgb(17,17,17)"><font face="arial, sans-serif"><br></font></span></div><div><font face="arial, sans-serif"><span style="color:rgb(17,17,17)"><b>Host</b>: </span><a href="mailto:madhurt@ttic.edu" target="_blank"><b>Madhur Tulsiani</b></a></font></div></div><div><div dir="ltr"><div dir="ltr"><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><br></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Sun, Jan 9, 2022 at 3:03 PM Mary Marre <<a href="mailto:mmarre@ttic.edu" target="_blank">mmarre@ttic.edu</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div dir="ltr"><div style="font-size:small"><div><div><p style="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> 11:00 am CT</b></font></font><br></font></p><p class="MsoNormal" style="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="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="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="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="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="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"><b>Title:</b> <span style="color:rgb(0,0,0)">Two Stories in Coding Theory</span> </font></p><div><font face="arial, sans-serif"><br></font></div><div><b><font face="arial, sans-serif">Abstract:</font></b></div><div><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">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="margin:0in 0in 8pt;line-height:12pt"><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">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><span style="color:rgb(17,17,17)"><font face="arial, sans-serif"><br></font></span></div><div><font face="arial, sans-serif"><span style="color:rgb(17,17,17)"><b>Host</b>: </span><a href="mailto:madhurt@ttic.edu" target="_blank"><b>Madhur Tulsiani</b></a></font></div><div><font face="arial, sans-serif"><br></font></div></div><div><div dir="ltr"><div dir="ltr"><br></div></div></div></div><div><div dir="ltr"><div dir="ltr"><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><br></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Mon, Jan 3, 2022 at 6:29 PM Mary Marre <<a href="mailto:mmarre@ttic.edu" target="_blank">mmarre@ttic.edu</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div><div><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"><b>Title:</b> <span style="color:rgb(0,0,0)">Two Stories in Coding Theory</span> </font></p><div><font face="arial, sans-serif"><br></font></div><div><b><font face="arial, sans-serif">Abstract:</font></b></div><div><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">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">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><span style="color:rgb(17,17,17)"><font face="arial, sans-serif"><br></font></span></div><div><font face="arial, sans-serif"><span style="color:rgb(17,17,17)"><b>Host</b>: </span><a href="mailto:madhurt@ttic.edu" target="_blank"><b>Madhur Tulsiani</b></a></font></div><div><font face="arial, sans-serif"><br></font></div></div><div><div dir="ltr"><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>
</blockquote></div></div>
</blockquote></div></div>
</blockquote></div></div>