Research Felds

The laboratory’s research areas include:

1.    Computational Complexity. An important branch of theoretical computer science that includes Boolean circuit complexity, communication and information complexity.

2.    Information Theory, mainly Algorithmic Information Theory (Kolmogorov Complexity). The laboratory continues the research tradition originated by Andrey Kolmogorov and his group.

3.    Algorithmic Statistics. A field closely related to Kolmogorov Complexity. Nikolay Vereshchagin is a co-founder of this field.

4.    Theory of Algorithms. This area mainly studies the algorithmic complexity of individual problems and is closely linked to applied computer science.

5.    Combinatorial Optimisation and Algorithmic Game Theory.