[Colloquium] [Talks at TTIC] 1/29 Research at TTIC: Saeed Seddighin, TTIC

[Alicia McClarin]

*When:*     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!

*Where:*    Zoom Virtual Talk (see details below)

*Who: *      Saeed Seddighin, TTIC

*Title: *      Dynamic Longest Increasing Subsequence and the
Erd\"{o}s-Szekeres Partitioning Problem

*Abstract: *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:
     (i) add an element,
     (ii) remove an element,
     or (iii) substitute an element for another.
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$.

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$.

----------------------------------------------------------------------------------------------------------
Register in advance for this meeting:
https://uchicagogroup.zoom.us/meeting/register/tJ0ocu-spz0vGN1xwYqc8tvA2eLCDVvp-Pb4

After registering, you will receive a confirmation email containing
information about joining the meeting.

********************************************************************************************

*Research at TTIC Seminar Series*

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.

To receive announcements about the seminar series, please subscribe to the
mailing list: https://groups.google.com/a/ttic.edu/group/talks/subscribe

Speaker details can be found at: http://www.ttic.edu/tticseminar.php.

For additional questions, please contact Nathan Srebro at nati at ttic.edu
<mcallester at ttic.edu>.

-- 
*Alicia McClarin*
*Toyota Technological Institute at Chicago*
*6045 S. Kenwood Ave.*
*Chicago, IL 60637*
*www.ttic.edu* <http://www.ttic.edu/>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20210122/e8ae5a48/attachment.html>