Algorithms and Complexity

Theoretical Computer Science forms the foundations of computing. One of its primary aims is to provide a mathematically grounded theory for developing sophisticated algorithms for real-world problems. This includes mathematical modelling of algorithmic approaches, estimation of the complexity of computational problems, and understanding the limits of efficient computation through computational complexity.

Our research

The Algorithms and Complexity theme is led by Professor Kristina Vušković. Research within the theme includes graph theory, logic and model theory, combinatorial optimisation, scheduling theory, algorithms on graphs and data structures, the computational complexity of problems on discrete structures, randomised algorithms, probabilistic analysis of algorithms and approximation algorithms.

The research interests of the individual members include:

• Dr Bogdan Alecu: Structural graph theory, hereditary classes, permutation patterns.
• Dr Dibyayan Chakraborty: Graph theory, Graph algorithms, algorithmic and structural aspects of geometric intersection graphs, approximation algorithms.
• Emeritus Professor Martin Dyer: Sampling and counting, randomised algorithms, Markov chains, complexity theory, constraint satisfaction problems, random structures, probabilistic analysis, combinatorial optimisation.
• Dr Noleen Koehler: Graph algorithms, parametrised complexity, property testing, algorithmic model theory.
• Professor Dillon Mayhew: Matroid theory, graph theory, second-order monadic logic, and complexity theory and computability theory for graphs and matroids.
• Dr Haiko Muller: Algorithms on graphs and partially ordered sets, fixed parameter algorithms, approximation algorithms, graph theory, special classes of graphs, width parameters of graphs.
• Dr Sebastian Ordyniak: Algorithms, complexity, parameterized algorithms, graphs, logic, knowledge representation, mixed integer linear programming, planning.
• Dr Fahad Panolan: Parameterized algorithms and complexity, graph algorithms, streaming algorithms, approximation algorithms.
• Dr Sanjukta Roy: Algorithms, computational social choice, stable matching, voting theory, hedonic games, fair division, parameterized algorithms, graph algorithms, algorithmic game theory.
• Dr Natasha Shakhlevich: Deterministic scheduling theory, scheduling with controllable parameters, scheduling algorithms for distributed computing.
• Professor Kristina Vušković: Structural graph theory and graph algorithms.
• Dr Samuel Wilson: Computer science education, mathematics education, education policy. 

We also have a large and lively group of postgraduate research students and postdoctoral fellows. We have been very successful in obtaining support from EPSRC and other funders and maintain a high number of international research collaborations. For further information, please see our group’s pages.

Contact us

If you are interested in collaborating with us or joining our research team, please contact Professor Kristina Vušković.