Skip to main content

Centre for Algorithms and Complexity

Centre for Algorithms and Complexity

Centre for Algorithms and Complexity

We conduct research regarding the design and analysis of algorithms of all kinds, as well as research in computational complexity more broadly.

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.

Explore Royal Holloway

Get help paying for your studies at Royal Holloway through a range of scholarships and bursaries.

There are lots of exciting ways to get involved at Royal Holloway. Discover new interests and enjoy existing ones.

Heading to university is exciting. Finding the right place to live will get you off to a good start.

Whether you need support with your health or practical advice on budgeting or finding part-time work, we can help.

Discover more about our academic departments and schools.

Find out why Royal Holloway is in the top 25% of UK universities for research rated ‘world-leading’ or ‘internationally excellent’.

Royal Holloway is a research intensive university and our academics collaborate across disciplines to achieve excellence.

Discover world-class research at Royal Holloway.

Discover more about who we are today, and our vision for the future.

Royal Holloway began as two pioneering colleges for the education of women in the 19th century, and their spirit lives on today.

We’ve played a role in thousands of careers, some of them particularly remarkable.

Find about our decision-making processes and the people who lead and manage Royal Holloway today.