The Centre is concerned with the study of various kinds of algorithms – parameterised, exact, randomised, heuristic and approximate – for problems arising in a multitude of areas such as graph theory, constraint satisfaction, combinatorial optimisation, and artificial intelligence.   

Our current focus includes theoretical research into parameterized algorithms and computational complexity, and applied research in access control in information security.  See below for a more precise list of areas. 

Computational complexity theory 

We are interested in classical and parameterized complexity, complexity of satisfiability, proof complexity, applications of logic in computer science, the interplay between algebra and computation, and the theory of SAT-solving. 

Graph theory and algorithms 

We are interested in directed, undirected, random, weighted, signed and other types of graphs as well as their generalizations such as hypergraphs, hypertournaments and directed hypergraphs. We study structural properties of graphs, algorithms on graphs and applications of graphs. 

A recent book "Classes of Directed Graphs", edited by J. Bang-Jensen and G. Gutin (Springer, 2018, in print) consists of chapters devoted to various important classes of directed graphs and written by experts in these classes of digraphs.

Access control in information security 

We are interested in various access control problems. In particular, we have done significant research on the Workflow Satisfiability Problem, WSP (aka Constraint Satisfaction Problem in access control).  We designed efficient theoretical and practical algorithms to solve WSP and its generalization, the Bi-Objective WSP, which allows us to decide in cases when the WSP is unsatisfiable. We studied various constraints for WSP, introducing the wide family of user-independent constraints, and studied resilience in WSP models. Our members received best papers awards at SACMAT 2015 and 2016 for WSP research. 

Constraint satisfaction problems  

Constraint satisfaction problems arise in many areas. For example, the problems of scheduling a collection of tasks, or laying out a silicon chip, or indeed the Workflow Satisfability Problem from access control mentioned above, can all be formulated as CSPs. In any CSP there are variables which all have to be assigned values, subject to specified constraints. An equivalent way of defining CSPs is via homomorphisms between relational structures. We are interested understanding the computational complexity of constraint satisfaction problems; in particular, when CSPs and their generalizations (such as Valued CSPs) can be solved by efficient algorithms. 

This covers not only questions of P-vs-NP characterisations, which are by now largely well understood, but also aspects such as "hybrid" structural restrictions and (in particular) questions of parameterized complexity of these problem variants. 

Algorithmic Game Theory  

We are interested in various problems emerging from game theory, economics, fair division, and computational social choice. We study their solution concepts and we derive efficient algorithms for them, exact or parameterized, or we prove that no such algorithms exist under suitable complexity-theoretic assumptions. Examples of such problems: computation of Nash equilibria, fair division of divisible and indivisible resources, facility location games. 

Quantum Computing

We are interested in theoretical aspects of quantum computing which is at the intersection of computer science, maths and physics research. We particularly study topics in quantum algorithms, quantum foundations, and quantum many-body systems from a computational perspective.

Core Academic Staff

Associate Member