Automata, Computability and Complexity Theory

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). The study of abstract machines and automata plays essential role in theoretical analysis of computations and therefore is important integral part of this stream of research.

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. Also we are open to interdisciplinary research and new collaborations on algorithmic and complexity aspects for various computational problems.

The group is led by Professor Igor Potapov