Algorithms, Complexity Theory and Optimisation Group

This is the home page of the Algorithms, Complexity Theory and Optimisation Group, part of the Algorithms Section in the Department of Computer Science at the University of Liverpool.

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)
  • what amount of computational resources such as time and space are required to perform those computations (computational complexity theory)
  • the broad area of algorithms, 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, 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

About the Algorithms, Complexity Theory and Optimisation Group

Staff and students
Our research projects