Algorithms, Complexity Theory and Optimisation

The question “What can be (efficiently) automated?” is one of the most inspiring philosophical and practical questions. Our group works on fundamental questions about what can be computed in principal (computability theory) and what amount of computational resources such as time and space are required to perform those computations (computational complexity theory), together with the broad area of algorithms and optimisation and their applications. . The study of abstract machines and automata plays an essential role in the theoretical analysis of computations and is an integral part of this stream of research. Our research group also focuses on practical and theoretical applications for algorithms, and places particular emphasis on the development of optimisation models and theoretical techniques for the design and analysis of algorithms for these optimisation models.

We have a wide range of expertise including such areas as analysis of algorithms, computational complexity, models of computations, mathematical logic, automata theory, automata and games, formal languages, probabilistic computation, computational geometry and topology, computational algebra, decision problems and reachability problems in infinite state systems, combinatorial optimisation, approximation algorithms, on-line algorithms, graph optimisation problems, mathematical programming, distributed approximation, optimisation problems in economics.

We are actively working on several interdisciplinary projects and open to new collaborations on algorithmic and complexity aspects for various computational problems that appear in other areas including chemistry, physics, biology, economics, engineering, etc.

The group is led by Professor Igor Potapov