Centre for Efficient Algorithms and Data Structures

Centre for Efficient Algorithms and Data Structures (EADS)

Headed by Professor Mikkel Thorup, Dept. Computer Science at the University of Copenhagen (DIKU), supported by an Advanced Grant from the Danish Council for Independent Research (FNU) under the Sapere Aude research carrier programme.

In efficient algorithms and data structures we are trying to understand the limits of computation. One of the many challenges is to understand the use and need of randomness. As a simple example, computers use randomness to decide where to store data in memory. This generally gives a nice even distrubution, not overloading any particular part of memory. However, if we just toss data into memory at random, how will we later find the data associated with a person, e.g., his phone number? What we want is a so-called hash function h that associates a "random" memory address h(x) with each name x. Unfortunately, it is impossible to implement a fully random function h, so instead we try to implement hash functions with some of the same good probabilistic properties as truly random functions, or we try to find a solution that altogether avoids the need of randomness, or prove that this is impossible. The general area is a nice combination of algorithms, graph theory, combinatorics, probability, and basic number theory.

Participants

  • Mikkel Thorup, Professor, Centre Head,
  • Stephen Alstrup, Professor, Deputy Head,
  • Christian Wulff-Nilsen, Assistant Professor,
  • Søren Dahlgaard, PhD Student,
  • Mathias Bæk Tejs Knudsen, PhD Student,
  • Esben Bistrup Halvorsen, PostDoc,
  • Eva Rotenberg, PhD Student,
  • Mikkel Abrahamsen, PhD Student,
  • Jacob Holm, PhD Student,
  • Anna Adamaszek, PostDoc,
  • Morten Stöckel, PostDoc

Funding

The original Advanced Grant application to Sapere Aude presenting the basic rationale is found here. Besides this grant, the members participate in Professor Carsten Thomassen's FNU project AlgoDisc - Discrete Mathematics, Algorithms, and Data Structrues. We also have an  International Network Programme with the CS department at  Princeton University represented by Prof. R. E. Tarjan.

Publications via DBLP (click here)

Projects