Information Theory

Many of the problems studied concern fundamental mathematical structures and their properties and are often motivated by applications in ICT.

The origin of the work can be traced back to a PhD thesis on covering codes from 1993. The early work on combinatorial and computer-aided construction methods for such codes was later extended to general coding theory, design theory, graph theory, Shannon theory, and combinatorial algorithms, that is, it is now touching large parts of discrete mathematics and information theory.

The questions studied are commonly about:

• existence – do certain structures exist?
• counting – how many are there?
• classification –what do they look like, up to symmetry?

The team is particularly known for its work on classifying mathematical structures up to symmetry [P. Kaski & P.R.J. Östergård, Classification Algorithms for Codes and Designs, Springer, Berlin, 2006]. The main achievements include enumeration of Steiner triple systems of certain small orders, the discovery of a q-analog of a Steiner triple system of order 13, showing nonexistence of a McLaughlin geometry, and classifying the perfect binary one-error-correcting codes of length 15, as well as algorithms and software (Cliquer) for clique problems in graphs.

Massive computations require massive computational resources. The team is a regular user of computational resources made available by the department, the school, the university, CSC, and others. The team has a computer cluster of its own, called Medusa (a monster in Greek mythology described as having the face of a woman with snakes in place of hair), with a total of more than 650 processor cores.

The work is supported in part by the Academy of Finland.

Contact

The research team is led by Professor Patric Östergård.