Data structures and lower bounds – the way to optimal search engines

PhD defence, Friday 17 May 2013. Kasper Green Larsen.

2013.05.17 | Nanna Maria Elgaard Pedersen

Kasper Green Larsen

During the course of his PhD studies, Kasper Green Larsen carried out research into data structures. This field deals with how efficiently data can be represented on a computer. Efficiency is typically measured in terms of how rapidly different data characteristics can be extracted, how much memory the computer uses to represent data, and how quickly data updates can be supported.

Efficient data structures are one of the supporting columns of the modern information society. All computer programs consist deep down of a collection of basic data structures, and it is typically these that set limits for the speed of the program. A slight improvement of these fundamental data structures would therefore lead to faster computer programs all over the world. This is why researchers have been trying for many decades to improve the known solutions. But when will it end? Is it always possible to improve the known solutions? Or is there a limit to how efficiently a data structure problem can be solved? This question is precisely what lower bounds are all about. Lower bounds are mathematical formulae that provide information about how efficiently (or inefficiently ) a given data structure problem can be solved.

In his studies, Kasper Green Larsen developed new mathematical methods to show lower bounds for data structures. These methods have been used to show the strongest known lower bounds ever since the field began in the 1970s. The lower bounds he achieved make it possible to conclude that a number of fundamental data structure problems cannot be solved more efficiently than the solutions known today. There is therefore no reason to start spending more energy on trying to find more efficient solutions to these problems.

The PhD degree was completed at the Department of Computer Science, Science and Technology, Aarhus University.

Time: Friday 17 May 2013 at 14.15
Place: Large Lecture Theatre, building 5510, room 103, Department of Computer Science, Aarhus University
Title of dissertation: Models and Techniques for Proving Data Structure Lower Bounds
Contact information: Kasper Green Larsen,
Members of the assessment committee:
Professor Valerie King, Department of Computer Science, University of Victoria, Canada
Professor Mikkel Thorup, Department of Computer Science, University of Copenhagen
Professor Peter Bro Miltersen (chair), Department of Computer Science, Aarhus University
Main supervisor:
Professor Lars Arge, Department of Computer Science, Aarhus University
Language: The dissertation will be defended in English

The defence is public.
The dissertation is available for reading at the Graduate School of Science and Technology/GSST, Ny Munkegade 120, building 1521, room 112, 8000 Aarhus C.

PhD defence
Comments on content: 
Revised 22.06.2017