BEGIN:VCALENDAR
CALSCALE:GREGORIAN
PRODID:iCalendar-Ruby
VERSION:2.0
BEGIN:VEVENT
DESCRIPTION: Binary search trees (BSTs) and heaps are perhaps the simplest 
 implementations of the dictionary and the priority queue data types. They a
 re among the most extensively studied structures in computer science\, yet\
 , many basic questions about them remain open. What is the best strategy fo
 r updating a BST in response to queries? Is there a single strategy that is
  optimal for every possible scenario? Are self-adjusting trees ("splay tree
 s"\, Sleator\, Tarjan\, 1983) optimal? In which cases can we improve upon t
 he logarithmic worst-case cost per operation?    Our understanding of heaps
  is even more limited. Fibonacci heaps (and their relatives) are theoretica
 lly optimal in a worst-case sense\, but they perform operations outside the
  "pure" comparison-based heap model (in addition to being complicated in pr
 actice). Is there a simple\, "self-adjusting" alternative to Fibonacci heap
 s? Is there\, by analogy to BSTs\, a heap that can adapt to regularities in
  the input? Are the two problems related?    In my talk I will present some
  old and new results pertaining to this family of questions. 
DTSTAMP:20181120T171000
DTSTART:20181203T141500
CLASS:PUBLIC
LOCATION:Freie Universität Berlin \n Institut für Informatik \n Takustr. 9 
 \n 14195 Berlin \n Room 005 (Ground Floor)
SEQUENCE:0
SUMMARY:László Kozma (Freie Universität Berlin): Self-adjusting data struct
 ures: trees and heaps
UID:94649660@/www.mi.fu-berlin.de
URL:https://www.mi.fu-berlin.de/en/facetsofcomplexity/monday/20181203-L-Koz
 ma.html
END:VEVENT
END:VCALENDAR