School of Informatics

Algorithms and Complexity Group

Laboratory for Foundations of Computer Science

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 Algebra, 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.

Academic staff

  • Mary Cryan
    Randomized algorithms (especially for sampling and counting); learning theory; computational biology.
  • Ilias Diakonikolas
    Algorithms, Computational Complexity, Learning, Game Theory.
  • Kousha Etessami
    automated verification, 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.
  • Kyriakos Kalorkoti
    Computational complexity, computer algebra, decision problems in group theory.
  • Elham Kashefi
    Models of quantum computing and their structural relations, exploring new applications, algorithms and cryptographic protocols for quantum information processing devices.
  • Richard Mayr
    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.
  • Rahul Santhanam
    Computational Complexity.

External Members

  • 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.
  • Martin Lotz (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.

Postdoctoral Fellows

  • Vaclav Brozek (Newton Fellow)
    Algorithms for MDPs and stochastic games, infinite-state systems, automata theory, model checking.
  • Maurice Jansen
    Algebraic complexity

Past Faculty

  • Amin Coja-Oghlan (now at DIMAP, University of Warwick)
    Random structures and algorithms.
  • Mark Jerrum (now at QMUL)
    Computational complexity, randomised algorithms, stochastic processes, random structures.

PhD Students

Recently-graduated PhDs

  • James Matthews, now working at Barco, Edinburgh.
  • Dominik Wojtczak, (now at U. of Liverpool) .

Graduate-Level courses