<div dir="ltr"><div dir="ltr"><div class="gmail_default" style="font-family:georgia,serif;font-size:small;color:rgb(0,0,0)"><b><font style="vertical-align:inherit"><font style="vertical-align:inherit">When:    </font></font></b><font style="vertical-align:inherit"><font style="vertical-align:inherit"> Monday, May 12th at <b><font style="background-color:rgb(255,255,0)">10:30 AM CT</font></b></font></font></div><div><div><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="georgia, 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="georgia, serif" color="#000000"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><b>Where:    </b><span class="gmail_default"><b></b></span><span class="gmail_default">T</span></font></font>alk will be given <font style="font-weight:bold"><u style="background-color:rgb(255,255,0)">live, in-person</u></font><font style="font-weight:bold"> </font>at</font></p><p class="MsoNormal" style="margin:0in;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font color="#000000" face="georgia, serif">                     TTIC, 6045 S. Kenwood Avenue</font></p><p class="MsoNormal" style="margin:0in;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font color="#000000" face="georgia, serif">                     5th Floor, Room 530<b> </b></font></p><p class="MsoNormal" style="margin:0in;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font color="#000000" face="georgia, serif"><b><br></b></font></p><p class="MsoNormal" style="margin:0in;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="georgia, serif" color="#000000"><span class="gmail_default"><b>Virtually:  </b>via Panopto<b> </b>(<a href="https://uchicago.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=bc9cc75b-866b-4915-a52a-b2480121118b" target="_blank">Livestream</a>) </span><b><br></b></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="georgia, 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="georgia, serif"><font color="#000000"><b><font style="vertical-align:inherit"><font style="vertical-align:inherit">Who:      <span class="gmail_default"></span>   </font></font></b><span class="gmail_default"></span>Toniann </font>Pitassi<font color="#000000">, Columbia University</font></font></p></div><div><b><font face="georgia, serif" color="#000000"><br></font></b></div><div><font face="georgia, serif" color="#000000"><b>Title:        </b>Strong Cell Probe Lower Bounds via Local PRGs</font></div><div><p></p><div><font face="georgia, serif" color="#000000"><b>Abstract:  </b>In this talk, we observe a tight connection between three topics: $NC^0$ cryptography, $NC^0$ range avoidance, and static data structure lower bounds. Using this connection, we leverage techniques from the cryptanalysis of $NC^0$ PRGs to prove state-of-the-art results in the latter two subjects. Our main result is a quadratic improvement (for space as a function of time) to the best cell probe lower bounds, breaking a longstanding barrier. We then utilize our explicit cell probe lower bounds to obtain the best known unconditional algorithms for $NC^0$ range avoidance: we can solve any instance with stretch n ↦ m in polynomial time once $m >> n^2$ and with the aid of an NP oracle we can solve any instance with $m >> n^{t/2}$ when t is odd. Finally, using our main correspondence we establish novel barrier results for obtaining significant improvements to our cell probe lower bounds.</font></div><font face="georgia, serif" color="#000000"><br>This is joint work with Oliver Korten and Russell Impagliazzo.</font></div><div><font face="georgia, serif" color="#000000"><br></font><div><font face="georgia, serif" color="#000000"><b><span class="gmail_default"></span>Bio:</b>  Toniann Pitassi was the Bell Canada Chair in Information Systems, in the Department of Computer Science at the University of Toronto, as well as a faculty member of the Vector Institute for AI, and on the research leadership team at the Swartz-Reismann Institute for Technology and Society . She has recently joined Columbia University where her primary research interests are complexity theory, fairness and privacy in machine learning. She currently holds a 6 year visiting professorship at the Institute of Advanced Study in mathematics and is also a recipient of the 2021 EATCS research award.</font></div><div><font face="georgia, serif" color="#000000"><br></font></div><div><p style="box-sizing:border-box;border-radius:0px;margin:0px 0px 10px"><font face="georgia, serif" color="#000000"><span style="box-sizing:border-box;border-radius:0px;font-weight:700">Hos</span><b><span style="box-sizing:border-box;border-radius:0px">t:<span class="gmail_default"> <a href="mailto:avrim@ttic.edu" target="_blank">Avrim Blum</a></span></span></b></font></p></div></div><br clear="all"></div><div><br></div><span class="gmail_signature_prefix">-- </span><br><div dir="ltr" class="gmail_signature"><div dir="ltr"><b><font color="#3d85c6">Brandie Jones </font></b><div><div><div><font color="#3d85c6"><b><i>Executive </i></b></font><b style="color:rgb(61,133,198)"><i>Administrative Assistant</i></b></div></div><div><font color="#3d85c6">Toyota Technological Institute</font></div><div><font color="#3d85c6">6045 S. Kenwood Avenue</font></div><div><font color="#3d85c6">Chicago, IL  60637</font></div></div><div><font color="#3d85c6"><a href="http://www.ttic.edu" target="_blank">www.ttic.edu</a> <br></font></div><div></div></div></div></div>
</div>