[Colloquium] 12/5 TTIC Colloquium: Parinya Chalermsook, Aalto University

[Mary Marre via Colloquium]

When:     Monday, December 5th at 11:00 a.m.

Where:    TTIC, 6045 S. Kenwood Avenue, 5th Floor, Room 526

Who:       Parinya Chalermsook, Aalto University


Title:       Recent Progresses on the Optimality of Online Binary Search
Trees.

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.

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

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.


Host: *Julia Chuzhoy* <cjulia at ttic.edu>




For more information on the colloquium series or to subscribe to the
mailing list, please see http://www.ttic.edu/colloquium.php





Mary C. Marre
Administrative Assistant
*Toyota Technological Institute*
*6045 S. Kenwood Avenue*
*Room 504*
*Chicago, IL  60637*
*p:(773) 834-1757*
*f: (773) 357-6970*
*mmarre at ttic.edu <mmarre at ttic.edu>*
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20161128/ee336fc4/attachment.html>