Algorithms and Complexity Group
We are an active research group within the Lab for Foundations of Computer
Science, with main research interests in Randomized Algorithms
(especially algorithms for sampling and counting), Computer
Computational Complexity, Algorithmic Game Theory,
Algorithms for Verification,
Quantum Complexity and Cryptography,
- and with some interest in
most aspects of algorithms and complexity. We are always interested
in hearing from prospective graduate students (or anyone) with
interests in these areas.
Randomized algorithms (especially for sampling and counting);
learning theory; computational biology.
Algorithms, Computational Complexity, Learning, Game Theory.
algorithms and computational complexity theory,
algorithmic game theory,
analysis of probabilistic systems, Markov decision processes, stochastic games,
logic, automata theory, model checking,
analysis of infinite-state systems,
finite model theory.
Computational complexity, computer algebra, decision problems in group
Models of quantum computing and their structural relations,
exploring new applications, algorithms and cryptographic protocols
for quantum information processing devices.
Automated verification, automata and temporal logic, model-checking and
semantic equivalence checking, formal verification of real-time and
probabilistic systems, infinite-state Markov chains and stochastic games.
Coralia Cartis (Lecturer, School of Mathematics, U. Edinburgh)
computational complexity, large-scale nonconvex optimization, first- and second-order optimization
algorithms, compressed sensing and sparse approximation, numerical analysis.
(Research Fellow, School of Mathematics, U. Edinburgh)
complexity of convex optimization, compressed sensing,
algebraic complexity, computational algebra and geometry,
foundations of numerical analysis, combinatorics and probability.
Peter Richtarik (Lecturer, School of Mathematics, U. Edinburgh)
large-scale convex optimization, gradient methods, sparse optimization,
randomized algorithms in optimization, operations research.
- Vaclav Brozek (Newton Fellow)
Algorithms for MDPs and stochastic games, infinite-state
systems, automata theory, model checking.
- Maurice Jansen
Amin Coja-Oghlan (now at
University of Warwick)
Random structures and algorithms.
- Mark Jerrum
(now at QMUL)
Computational complexity, randomised algorithms, stochastic processes,
- James Matthews, now working at Barco, Edinburgh.
- Dominik Wojtczak, (now at U. of Liverpool) .