Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

New for: D1, D2, D3, D4, D5
<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Binary Search Trees, Precognition, and Patterns
Speaker:Parinya Chalermsook
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:
Event Type:Joint Lecture Series
Visibility:D1, D2, D3, D4, D5, SWS, RG1, MMCI
We use this to send out email in the morning.
Level:Public Audience
Date, Time and Location
Date:Wednesday, 11 November 2015
Duration:-- Not specified --
Building:E1 5
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.

Name(s):Jennifer Müller
EMail:--email address not disclosed on the web
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):
  • Christian Klein, 10/13/2016 04:11 PM
  • Parinya Chalermsook, 11/01/2015 06:53 PM
  • Parinya Chalermsook, 10/24/2015 12:14 PM
  • Parinya Chalermsook, 10/23/2015 02:31 AM
  • Jennifer Müller, 09/01/2015 09:44 AM -- Created document.