<div dir="ltr"><div dir="ltr"><div class="gmail_default" style="font-size:small"><div><b>When</b>:    Monday, July 15th from <span style="background-color:rgb(255,255,0)"><b>1</b><b>- 3 pm CT</b></span></div><div><b><br></b></div><div><b>Where</b>:  Talk will be given <b><font color="#0000ff">live, in-person</font></b> at<br>              TTIC, 6045 S. Kenwood Avenue<br>              5th Floor, <b><u><font color="#000000">Room 529</font></u></b><b><br></b><br><b>Virtually</b>: via <a href="https://uchicago.zoom.us/j/93804353690?pwd=xYnLgPPNFLrlPCi7DNLNB5QzqLmMQO.1" target="_blank"><b>Zoom</b></a> <br></div><div>                 </div><div><b>Who</b>:     <font face="tahoma, sans-serif">Shashank Srivastava, TTIC   </font><br><br></div><div><div class="MsoNormal" align="center" style="margin:0in 0in 8pt;text-align:center;line-height:15.6933px;font-size:11pt;font-family:Calibri,sans-serif"><hr size="2" width="100%" align="center"></div></div><div><div><div><font face="arial, sans-serif"><b>Title: </b>    Continuous Optimization for Decoding Errors</font></div><div><font face="arial, sans-serif"><br></font></div><div><font face="arial, sans-serif"><b>Abstract: </b></font><span style="font-family:arial,sans-serif">Error-correcting codes are one of the most fundamental objects in pseudorandomness, with applications in communication, complexity theory, and beyond. Codes are useful because of their ability to support decoding, which is the task of recovering a codeword from its noisy copy. List decoding is a relaxation where the decoder is allowed to output a list of codewords, and has seen tremendous progress over the last 25 years. In this thesis, we prove new algorithmic and combinatorial results about list decoding.</span><span style="font-family:arial,sans-serif"> </span><div><p><font face="arial, sans-serif">We describe a list decoding framework that reduces the task of efficient decoding to proving distance in certain restricted proof systems. We then instantiate this framework for Tanner codes of Sipser and Spielman [IEEE Trans. Inf. Theory 1996] and Alon-Edmonds-Luby (AEL) distance amplification [FOCS 1995] of unique decodable base codes to get the first polynomial time list decoding algorithms for both of these codes. We also discuss extensions to the quantum version of AEL distance amplification, yielding polynomial-time list decodable quantum LDPC codes.</font></p><p><font face="arial, sans-serif">We next give an alternate viewpoint of the list decoding framework based on abstract regularity lemmas instead of convex hierarchies. We show how to efficiently implement the regularity lemma for the case of Ta-Shma’s explicit codes near the Gilbert-Varshamov bound [STOC 2017]. This leads to a near-linear time algorithm for unique decoding for Ta-Shma’s codes.</font></p><p><font face="arial, sans-serif">We also give new combinatorial results that improve known list sizes beyond the Johnson bound. Firstly, we adapt the AEL amplification to construct a new family of explicit codes that can be combinatorially list decoded to the optimal error correction radius. This is the first example of such a code that does not use significant algebraic ingredients. Secondly, we present list size improvements for Folded Reed-Solomon codes, improving the state of the art list size among explicit list decoding capacity achieving codes.</font></p><p><font face="arial, sans-serif"><b>Thesis Committee: </b><a href="mailto:madhurt@ttic.edu" target="_blank">Madhur Tulsiani</a> (Thesis Advisor), Pravesh K. Kothari (Princeton University), Yury Makarychev</font></p></div></div></div><div><br></div></div><div><br></div><div><br></div><div><br></div></div><div><div dir="ltr" class="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, Rm 517</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><font size="1"><i><font face="arial, helvetica, sans-serif" color="#3d85c6">773-834-1757</font></i></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 Thu, Jul 4, 2024 at 1:08 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 style="font-size:small"><div><b>When</b>:    Monday, July 15th from <span style="background-color:rgb(255,255,0)"><b>1</b><b>- 3 pm CT</b></span></div><div><b><br></b></div><div><b>Where</b>:  Talk will be given <b><font color="#0000ff">live, in-person</font></b> at<br>              TTIC, 6045 S. Kenwood Avenue<br>              5th Floor, <b><u><font color="#000000">Room 529</font></u></b><b><br></b><br><b>Virtually</b>: via <a href="https://uchicago.zoom.us/j/93804353690?pwd=xYnLgPPNFLrlPCi7DNLNB5QzqLmMQO.1" target="_blank"><b>Zoom</b></a> <br></div><div>                 </div><div><b>Who</b>:     <font face="tahoma, sans-serif">Shashank Srivastava, TTIC   </font><br><br></div><div><div class="MsoNormal" align="center" style="margin:0in 0in 8pt;text-align:center;line-height:15.6933px;font-size:11pt;font-family:Calibri,sans-serif"><hr size="2" width="100%" align="center"></div></div><div><div><div><font face="arial, sans-serif"><b>Title: </b>    Continuous Optimization for Decoding Errors</font></div><div><font face="arial, sans-serif"><br></font></div><div><font face="arial, sans-serif"><b>Abstract: </b></font><span style="font-family:arial,sans-serif">Error-correcting codes are one of the most fundamental objects in pseudorandomness, with applications in communication, complexity theory, and beyond. Codes are useful because of their ability to support decoding, which is the task of recovering a codeword from its noisy copy. List decoding is a relaxation where the decoder is allowed to output a list of codewords, and has seen tremendous progress over the last 25 years. In this <span>thesis</span>, we prove new algorithmic and combinatorial results about list decoding.</span><span style="font-family:arial,sans-serif"> </span><div><p><font face="arial, sans-serif">We describe a list decoding framework that reduces the task of efficient decoding to proving distance in certain restricted proof systems. We then instantiate this framework for Tanner codes of Sipser and Spielman [IEEE Trans. Inf. Theory 1996] and Alon-Edmonds-Luby (AEL) distance amplification [FOCS 1995] of unique decodable base codes to get the first polynomial time list decoding algorithms for both of these codes. We also discuss extensions to the quantum version of AEL distance amplification, yielding polynomial-time list decodable quantum LDPC codes.</font></p><p><font face="arial, sans-serif">We next give an alternate viewpoint of the list decoding framework based on abstract regularity lemmas instead of convex hierarchies. We show how to efficiently implement the regularity lemma for the case of Ta-Shma’s explicit codes near the Gilbert-Varshamov bound [STOC 2017]. This leads to a near-linear time algorithm for unique decoding for Ta-Shma’s codes.</font></p><p><font face="arial, sans-serif">We also give new combinatorial results that improve known list sizes beyond the Johnson bound. Firstly, we adapt the AEL amplification to construct a new family of explicit codes that can be combinatorially list decoded to the optimal error correction radius. This is the first example of such a code that does not use significant algebraic ingredients. Secondly, we present list size improvements for Folded Reed-Solomon codes, improving the state of the art list size among explicit list decoding capacity achieving codes.</font></p><p><font face="arial, sans-serif"><b><span>Thesis</span> Committee: </b><a href="mailto:madhurt@ttic.edu" target="_blank">Madhur Tulsiani</a> (<span>Thesis</span> Advisor), Pravesh K. Kothari (Princeton University), Yury Makarychev</font></p></div></div></div><div><br></div></div><div><br></div><div><br></div></div><div><div dir="ltr" class="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, Rm 517</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><font size="1"><i><font face="arial, helvetica, sans-serif" color="#3d85c6">773-834-1757</font></i></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>