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 Kristina Vušković. Research within the theme includes graph theory, algorithms on graphs and discrete structures, the computational complexity of problems on discrete structures, logic and proof complexity, deterministic scheduling theory and its applications, randomised algorithms, probabilistic analysis of algorithms, approximation algorithms and combinatorial optimisation.
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".
- Olaf Beyersdorff: Computational complexity, propositional proof complexity, satisfiability problems, bounded arithmetic, non-classical logics.
- Martin Dyer: Sampling and counting, randomised algorithms, Markov chains, complexity theory, constraint satisfaction problems, random structures, probabilistic analysis, combinatorial optimisation.
- 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.
- Haiko Muller: Algorithms on graphs and partially ordered sets, fixed parameter algorithms, approximation algorithms, graph theory, special classes of graphs, width parameters of graphs.
- Natasha Shakhlevich: Deterministic scheduling theory, scheduling with controllable parameters, scheduling algorithms for distributed computing.
- Kristina Vušković: Structural graph theory with algorithmic consequences.
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.
Jointly with the School of Mathematics, we organise the Algorithms, Logic, and Algebra seminars.
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ć.
A New Dawn of Intuitionism: Mathematical and Philosophical Advances
PIs: Professor Michael Rathjen and Professor Olaf Beyersdorff
John Templeton Foundation, 2017-2020
Train unit scheduling optimisation (2014-2018)
PI: Dr Raymond Kwan
Sponsor: First Rail Holdings Ltd
Correctness by Construction (2014-2017)
Coordinator: Professor Olaf Beyersdorff
Funder: EU, Marie Curie International Research Staff Exchange Scheme
Graph Structure Theory and Algorithmic Applications (2011-2016)
PI: Dr Isolde Alder
Funder: German Research Council