Abstract
The field of data structures is concerned 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 bearing pillars of our modern
information society and researchers have been trying for many decades to
develop faster data structures. But is there a limit to how efficiently a
data structure problem can be solved? This question is precisely what
lower bounds address.

The holy grail is of course to prove lower bounds that tells us, that the
data structure solutions we have known since the 70s cannot be improved
any further. Unfortunately, as we shall see in this lecture, we are very
far from achieving this goal. After more than 30 years of research, the
state-of-the-art in data structure lower bound techniques can prove tight
bounds for only a handful of data structure problems.

In this talk, I start by giving an overview of the history and most ground
breaking results in proving data structure lower bounds. I then give a
high level presentation of one of my own research results, proving the
strongest data structure lower bound to date. This result received the
best paper award and the best student paper award (the Danny Lewin's
award) at STOC'12: 44th ACM Symposium on Theory of Computing.

Towards the end of the talk, I will change subject and talk about some new
lines of research that have caught my attention recently. This includes in
particular problems in bioinformatics and machine learning.

Bio:
Kasper Green Larsen obtained his ph.d. at Aarhus University in 2013, under
the supervision of Professor Lars Arge. During his studies, Kasper
published 19 papers and received a number of awards for his research,
including e.g. the FOCS'11 best student paper award (the Machtey award),
the STOC'12 best paper and best student paper award (the Danny Lewin's
award) award, a Google European Doctoral Fellowship and the Danish
Minister of Science's EliteForsk travel scholarship that he used to visit
Turing award winner Robert Tarjan at Princeton University in 2011. After
his ph.d. Kasper joined the bioinformatics company CLC bio, a QIAGEN
Company, as Scientific Software Developer.