BARC talk by Laszlo Kozma

Wednesday, 23 March 2022, Laszlo Kozma, Assistant Professor at Freie Universität Berlin, Germany, will give a talk on "Search trees on trees".

Title:
Search trees on trees

Abstract:
"search trees on graphs" (STGs) and "search trees on trees" (STTs) generalize binary search trees (BSTs) and allow the  exploration of graph- or tree-shaped search spaces. They have been studied under various guises in computer science and combinatorics (closely related concepts include vertex rankings, elimination trees, ordered colorings, treedepth, and graph associahedra). For BSTs a rich theory of adaptivity has been developed in the past decades: an optimal tree for a given
search distribution can be efficiently computed [Knuth, '71], and dynamically updated trees, e.g. splay trees, have adaptive properties even in an online setting [Sleator, Tarjan, '83]. It is natural to ask to what extent this theory extends to the more general case of STTs. I will review results in this area, including recent joint work with Benjamin Berendsohn.

Bio:
Laszlo is a researcher in computer science, interested in data structures, algorithms, combinatorics, and other related (and unrelated) topics. Since 2018 he has been working as an assistant professor at Freie Universität Berlin, in theTheoretical Computer Sciencegroup.
He obtained his PhD at Saarland Universityin Saarbrücken, Germany, where his advisor was Raimund Seidel. Afterwards Laszlo spent a year as a postdoc at Tel Aviv University, hosted by Haim Kaplan and Yossi Azar, and a year at TU Eindhoven, hosted by Nikhil Bansal. Prior to this he worked and studied at Helsinki University of Technology (later renamed Aalto University), and TU Cluj in Romania, where he is from.