As brief as possible, this ordered list of (overlapping) areas characterize
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.
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,
bin packing (fair and unfair variants),
packet bundling (dynamic TCP acknowledgment),
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
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.
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