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.
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, randomized algorithms, probabilistic analysis of algorithms and approximation algorithms.
The research interests of the individual members include:
- Isolder Adler: Structure of graphs and hypergraphs, logic and model theory, (parameterised) complexity theory, database theory, combinatorial games, theory of "big data". Publications
- Martin Dyer: Sampling and counting, randomised algorithms, Markov chains, complexity theory, constraint satisfaction problems, random structures, probabilistic analysis, combinatorial optimisation. Publications
- Raymond Kwan: Public transport scheduling, integer linear programming, heuristics, meta-heuristics, hyper-heuristics. The research has led to Tracsis Plc, a Leeds University spin-out company. Publications
- Haiko Muller: Algorithms on graphs and partially ordered sets, fixed parameter algorithms, approximation algorithms, graph theory, special classes of graphs, width parameters of graphs. Publications
- Natasha Shakhlevich: Deterministic scheduling theory, scheduling with controllable parameters, scheduling algorithms for distributed computing. Publications
- Kristina Vušković: Structural graph theory and graph algorithms. Publications
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 (see grants).
Jointly with the School of Mathematics, we organise the Algorithms, Logic, and Algebra seminars.
Logic discussion group
This discussion group is open to researchers and postgraduate students with an interest in logic and its applications.
We have opportunities for prospective PhD students including a number of studentships. This list is by no means definitive and you should feel free to contact the group to discuss your own interests. However, applicants should note that the research is inherently mathematical, and requires a background and interest in mathematics and/or the mathematical aspects of computer science.
If you are interested in collaborating with us or joining our research team, please contact Professor Kristina Vušković.