Research Interests
As brief as possible, this ordered list of (overlapping) areas characterize
my interests:
Online Algorithms,
Data Structures,
Database Systems,
Algorithmics.
A slightly more detailed description is given below, and some
impression can be obtained by checking
my publication list,
list of students,
and list of courses.
Online Algorithms
My primary interest has been performance measures;
in particular the accommodating function and
relative worst order analysis.
Along the way, I have worked with many concrete online problems,
including
bin packing (fair and unfair variants),
call control,
inventory management,
k-server,
list accessing,
packet bundling (dynamic TCP acknowledgment),
paging,
scheduling,
seat reservation,
and
unit clustering.
Data Structures
Most of my work in this area has dealt with search trees with relaxed
balance, involving variants of B-trees, AVL-trees, red-black trees,
and other structures.
I have also looked at chronological transcript operations
in persistent search trees as well as various amortized analysis issues
Database Systems
My work on search trees with relaxed balance came out of a database
index motivation. I have also worked on smooth incorporation of
grouping and domain value computation in relational algebra
and on various query optimization issues, limiting the need for
sorting of temporary results.
Algorithmics
In addition to the problems areas above (most of which fall under
the headline of algorithmics), I have touched upon the following:
-
Approximation algorithms in the form of a study of priority algorithms.
-
Algorithmic concurrency issues such as
packet routing on a network and
shared-memory locking protocols.
-
Semantic concurrency issues in the form of the first full abstractness results
for a non-interleaving denotational semantics for a process languages,
as well as some bisimulation model checking work.
-
Regular expressions with back referencing
-
Bounds for the number of products of affine combinations which
can be produced when elements can be arranged freely in matrices,
motivated by a technique for improving
the communication complexity of zero-knowledge proofs.
Last modified: Fri Jul 30 15:36:29 CEST 2010
Kim Skak Larsen
(kslarsen@imada.sdu.dk)