AG 1, AG 2, AG 3, AG 4, AG 5, SWS, RG1, MMCI   Info

Public Audience

English

-- Not specified --

Saarbrücken

Two challenges in real-world optimization problems are computational intractability (many problems are NP-hard), and uncertainty (input data are incomplete or change over time). In this talk, we will see a problem that encapsulates both challenges: What is the asymptotically best binary search tree (BST) data structure that responds to “real-time” input data? BSTs have played huge roles in computer science, both in research and in curriculum, so it is not a surprise that this problem is considered a flagship open problem in data structure. Resolving the problem is likely to impact the field of algorithms as a whole. Its difficulty is witnessed by the fact that even highly restricted special cases have remained unresolved for 3 decades.

I will report our recent progresses that, despite not resolving the problem, leapfrogged some long-standing barriers. The talk will be accessible by general audience: I will highlight the "conceptual" messages of our results, rather than technical/mathematical prowess.

The talk is based on joint work with Mayank Goswami, Laszlo Kozma, Kurt Mehlhorn, and Thatchaphol Saranurak.

Jennifer Müller

2900

--email hidden

passcode not visible

logged in users only