<div dir="ltr"><div><div style="font-size:12.8px"><font face="arial, helvetica, sans-serif"><span style="font-size:12.8px">When:</span><b style="font-size:12.8px"> </b><span style="font-size:12.8px">    </span><span style="font-size:12.8px">Monday, December 5th at 11:00 a.m.</span><span style="font-size:12.8px"> </span><br></font></div><div dir="ltr"><div style="font-size:12.8px"><font face="arial, helvetica, sans-serif"><br></font></div><div style="font-size:12.8px"><font face="arial, helvetica, sans-serif">Where:    TTIC, 6045 S. Kenwood Avenue, 5th Floor, Room 526</font></div><div style="font-size:12.8px"><font face="arial, helvetica, sans-serif"><br></font></div><div style="font-size:12.8px"><font face="arial, helvetica, sans-serif" style="font-size:12.8px">Who:       Parinya Chalermsook, Aalto University</font></div><div><font face="arial, helvetica, sans-serif"><br></font></div></div></div><div><font face="arial, helvetica, sans-serif"><br></font></div><div><font face="arial, helvetica, sans-serif">Title:       Recent Progresses on the Optimality of Online Binary Search Trees. </font></div><div><font face="arial, helvetica, sans-serif"><br></font></div><div><font face="arial, helvetica, sans-serif">Abstract: The dynamic optimality conjecture [Sleator and Tarjan,1985] is one of the most fundamental open problems in data structures. The conjecture postulates the existence of an asymptotically optimal online binary search trees (BST). Despite many attempts, even highly restricted consequences of the conjecture remained open for decades. These consequences not only serve as intermediate steps towards dynamic optimality, but they also shed some light on how BSTs can efficiently access structured input. </font></div><div><font face="arial, helvetica, sans-serif"><br></font></div><div><font face="arial, helvetica, sans-serif">In this talk, I will present our recent progresses on two such notorious consequences. Our first result establishes a new connection between binary search trees and an old concept of combinatorics, called pattern avoidance. This connection allows us to "resolve"  the traversal conjecture [Sleator and Tarjan, JACM 1985]. In another direction, we establish a connection between binary search trees and the k-server problem, thus partially addressing an open question by [Iacono, SODA 2000].   </font></div><div><font face="arial, helvetica, sans-serif"><br></font></div><div><font face="arial, helvetica, sans-serif">This is a joint work with Mayank Goswami, Laszlo Kozma, Kurt Mehlhorn, and Thatchaphol Saranurak. The first result appeared in FOCS 2015. The second result is a work in progress.</font></div><div><font face="arial, helvetica, sans-serif"><br></font></div><div><font face="arial, helvetica, sans-serif"><br></font></div><div><font face="arial, helvetica, sans-serif">Host: <a href="mailto:cjulia@ttic.edu"><b>Julia Chuzhoy</b></a></font></div><div><font face="arial, helvetica, sans-serif"><br></font></div><div><font face="arial, helvetica, sans-serif"><br></font></div><div><font face="arial, helvetica, sans-serif"><br></font></div><div><div style="font-size:12.8px"><font face="arial, helvetica, sans-serif"><br></font></div><div style="font-size:12.8px"><font face="arial, helvetica, sans-serif"><span style="font-size:12.8px">For more information on the </span><span style="font-size:12.8px">colloquium</span><span style="font-size:12.8px"> series or to subscribe to the mailing list, please see </span><a href="http://www.ttic.edu/colloquium.php" target="_blank" style="font-size:12.8px">http://www.ttic.edu/colloq<wbr>uium.php</a></font></div></div><div><font face="arial, helvetica, sans-serif"><br></font></div><div><font face="arial, helvetica, sans-serif"><br></font></div><div><br></div><div><br></div><div><br></div><div><div class="gmail_signature"><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><font face="arial, helvetica, sans-serif">Mary C. Marre</font><div><font face="arial, helvetica, sans-serif">Administrative Assistant</font></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6"><b>Toyota Technological Institute</b></font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">6045 S. Kenwood Avenue</font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Room 504</font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Chicago, IL  60637</font></i></div><div><i><font face="arial, helvetica, sans-serif">p:(773) 834-1757</font></i></div><div><i><font face="arial, helvetica, sans-serif">f: (773) 357-6970</font></i></div><div><b><i><a href="mailto:mmarre@ttic.edu" target="_blank"><font face="arial, helvetica, sans-serif">mmarre@ttic.edu</font></a></i></b></div></div></div></div></div></div></div></div></div></div>
</div>