About the Laboratory

The International Laboratory of Theoretical Computer Science was founded in December 2015 at the HSE Faculty of Computer Science. Structurally, it is part of the Big Data and Information Retrieval School.

The laboratory’s primary aim is to strengthen and develop the group of researchers actively working and teaching in theoretical computer science at HSE, and to support them in conducting cutting-edge research. Facilitating international collaboration is another key goal: the laboratory staff work as part of the global theoretical computer science community.

The laboratory’s primary mission is to conduct research in theoretical computer science.

The laboratory’s research builds on the strengths already represented by the Moscow school of theoretical computer science and by the laboratory’s own staff and visitors.

Key research areas include:

1.    Computational Complexity. A modern and fast-growing branch of computer science that includes circuit complexity, communication and information complexity.

2.    Classical Information Theory, with a particular emphasis on Algorithmic Information Theory (Kolmogorov Complexity). The laboratory continues the research tradition originated by Andrey Kolmogorov and his group.

3.    Algorithmic Statistics. Nikolay Vereshchagin, a co-founder of this field, is the head of the laboratory.

4.    Theory of Algorithms. The design and analysis of algorithms.

5.    Combinatorial Optimisation and Algorithmic Game Theory. Vladimir Gurvich, a leading research fellow at the laboratory, is a renowned expert in this area and has a long-standing successful collaboration with Moscow mathematicians.

Although research is the laboratory’s main focus, its members actively participate in teaching, primarily in courses related to theoretical computer science.

The laboratory also provides an environment for student research projects at all levels (from undergraduate to graduate), carried out in collaboration with laboratory researchers and visiting scholars.