# 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

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 |