<div dir="ltr"><div><font face="arial, sans-serif" style="color:rgb(0,0,0)"><b>When:</b>     Friday, January 29th at 10:20am (please note that all times are in Central Standard Time); The room is open beginning at 10:00am and we encourage everyone to join early to mingle!</font></div><div style="color:rgb(0,0,0)"><font face="arial, sans-serif"><br></font></div><div style="color:rgb(0,0,0)"><font face="arial, sans-serif"><b>Where:</b>    Zoom Virtual Talk (see details below)<br></font></div><div><div style="color:rgb(0,0,0)"><p style="margin-bottom:0.0001pt;line-height:normal"><font face="arial, sans-serif"><b>Who: </b>      </font>Saeed Seddighin, TTIC</p><table cellpadding="0" style="border-collapse:collapse;margin-top:0px;width:auto;font-size:0.875rem;letter-spacing:0.2px;display:block"></table></div><div style="color:rgb(0,0,0)"><font face="arial, sans-serif"><br></font></div><div><font face="arial, sans-serif"><b style="color:rgb(0,0,0)">Title: </b><font color="#000000">      </font></font>Dynamic Longest Increasing Subsequence and the Erd\"{o}s-Szekeres Partitioning Problem</div><div><br></div><div><font face="arial, sans-serif"><b style="color:rgb(0,0,0)">Abstract: </b></font>In this talk, I'll discuss our new approximation algorithms for the dynamic variant of the longest increasing subsequence (\textsf{LIS}) problem. In this setting, operations of the following form arrive sequentially:</div>     (i) add an element, <div>     (ii) remove an element, </div><div>     or (iii) substitute an element for another.  </div><div>At every point in time, the algorithm has an approximation to the longest increasing subsequence.  We present a $(1+\epsilon)$-approximation algorithm for \textsf{DTM} with polylogarithmic worst-case  update time and a constant factor approximation algorithm for \textsf{LIS} with worst-case update time $\tilde O(n^\epsilon)$ for any constant $\epsilon > 0$.<br><br>Our dynamic algorithm for \textsf{LIS} leads to an almost optimal algorithm for the Erd\"{o}s-Szekeres partitioning problem. Erd\"{o}s-Szekeres partitioning problem was introduced by Erd\"{o}s and Szekeres in 1935 and was known to be solvable in time $O(n^{1.5}\log n)$. Subsequent work improves the runtime to $O(n^{1.5})$ only in 1998. Our dynamic \textsf{LIS} algorithm leads to a solution for Erd\"{o}s-Szekeres partitioning problem with runtime $\tilde O_{\epsilon}(n^{1+\epsilon})$ for any constant $\epsilon > 0$.</div><div><br></div><div style="color:rgb(0,0,0)"><font face="arial, sans-serif">----------------------------------------------------------------------------------------------------------</font></div><div style="color:rgb(0,0,0)">Register in advance for this meeting:</div><div style="color:rgb(0,0,0)"><a href="https://uchicagogroup.zoom.us/meeting/register/tJ0ocu-spz0vGN1xwYqc8tvA2eLCDVvp-Pb4" target="_blank">https://uchicagogroup.zoom.us/meeting/register/tJ0ocu-spz0vGN1xwYqc8tvA2eLCDVvp-Pb4</a><br><br>After registering, you will receive a confirmation email containing information about joining the meeting. </div><div style="color:rgb(0,0,0)"><font face="arial, sans-serif"><br></font></div></div><div style="color:rgb(0,0,0)"><div style="font-size:13px;margin:0px;line-height:normal"><font face="arial, sans-serif"><b style="font-size:12.8px">******************************************************************************************</b><br></font></div><div style="font-size:13px;margin:0px;line-height:normal"><div style="font-size:12.8px"><b><font face="arial, sans-serif"><br></font></b></div><div style="font-size:12.8px"><b><font face="arial, sans-serif">Research at TTIC Seminar Series</font></b></div><div style="font-size:12.8px"><font face="arial, sans-serif"> </font></div><div style="font-size:12.8px"><font face="arial, sans-serif">TTIC is hosting a weekly seminar series presenting the research currently underway at the Institute. Every week a different TTIC faculty member will present their research.  The lectures are intended both for students seeking research topics and adviser, and for the general TTIC and University of Chicago communities interested in hearing what their colleagues are up to.   </font></div><div style="font-size:12.8px"><font face="arial, sans-serif"> </font></div><div style="font-size:12.8px"><font face="arial, sans-serif">To receive announcements about the seminar series, please subscribe to the mailing list: <a href="https://groups.google.com/a/ttic.edu/group/talks/subscribe" style="text-decoration-line:none" target="_blank">https://groups.google.com/a/ttic.edu/group/talks/subscribe</a></font></div><div style="font-size:12.8px"><font face="arial, sans-serif"><br></font></div><div style="font-size:12.8px"><font face="arial, sans-serif">Speaker details can be found at: <a href="http://www.ttic.edu/tticseminar.php" style="text-decoration-line:none" target="_blank">http://www.ttic.edu/tticseminar.php</a>.</font></div><div style="font-size:12.8px"><font face="arial, sans-serif"> </font></div><div style="font-size:12.8px"><font face="arial, sans-serif">For additional questions, please contact Nathan Srebro at <a href="mailto:mcallester@ttic.edu" style="text-decoration-line:none" target="_blank">nati@ttic.edu</a>.</font></div></div></div><div><br></div>-- <br><div dir="ltr" data-smartmail="gmail_signature"><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><b><font color="#0b5394">Alicia McClarin</font></b></div><div dir="ltr"><div><div><font color="#0b5394"><i>Toyota Technological Institute at Chicago</i></font></div><div><div><font color="#0b5394"><i>6045 S. Kenwood Ave.</i></font></div><div><i style="color:rgb(11,83,148)">Chicago, IL 60637</i></div></div><div><a href="http://www.ttic.edu/" target="_blank"><font color="#0b5394"><i>www.ttic.edu</i></font></a></div></div></div></div></div></div></div></div></div></div></div></div>