Algorithms and Computational Complexity

Algorithms and Computational Complexity

We are an active research group within the Laboratory for Foundations of Computer Science, with main research interests in Randomized Algorithms (especially algorithms for sampling and counting), Spectral Graph Theory, Algorithms for Massive Graphs, 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 and businesses with interests in these areas.

An informal Algorithms Reading Group takes place during the semester on Wednesdays at 4pm-5.30pm.  

   

Academic staff

Mary CryanRandomized algorithms – especially for sampling and counting, learning theory, computational biology
Heng GuoTheoretical computer science – especially the complexity of counting problems for example, computing marginal probabilities and expectations of random variables, the evaluation of partition functions
Kousha EtessamiAutomated 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 KalorkotiComputational complexity, computer algebra, decision problems in group theory
Richard MayrAutomated 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
Rik SarkarMachine learning algorithms, network analysis, computational geometry: topology, trajectory analysis, distributed computing, data science
He SunAlgorithmic spectral graph theory, distributed algorithms, data streaming algorithms  

External/Part-time Academics

Jessica EnrightGraph theory, networks, and the application of theoretical computer science to controlling the spread of infectious disease
Elham KashefiModels of quantum computing and their structural relations, exploring new applications, algorithms and cryptographic protocols for quantum information processing devices

Current PhD Students

 Previously Graduated PhD Students

Alistair Stewart (2015)Efficient algorithms for infinite-state recursive stochastic models and Newton's methodhsdfhsdfhsdfhshshshsdfhsdh
Chiranjit Chakraborty (2014) Instance compression of parametric problems and related hierarchies
Lorenzo Clemente (2012)Generalized simulation relations with applications in automata theory
Páidí Creed (2010) Counting and sampling problems on Eulerian graphs
Grant Olney Passmore (2011) Combined decision procedures for nonlinear arithmetics, real and complex

Past Faculty

Ilias DiakonikolasNow at University of Southern California. Efficient algorithms for fundamental problems in machine learning
Rahul Santhanam Now at Oxford University. Computational complexity
Amin Coja-Oghlan Now at Frankfurt University. Random structures and algorithms.
Mark JerrumNow at QMUL. Computational complexity, randomised algorithms, stochastic processes, random structures.