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), 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 (or anyone) with interests in these areas.
During semester-time, we hold an informal "Algorithms reading
group" on Wednesdays 4pm-5:30pm.
Randomized algorithms (especially for sampling and counting);
learning theory; computational biology.
Theoretical computer science, especially the complexity of
counting problems (for example, computing marginal probabilities
and expectations of random variables, the evaluation of
partition functions, etc.).
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.
Computational complexity, computer algebra, decision problems in group
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.
Machine Learning algorithms, Network Analysis,
Computational Geometry: topology, and trajectory analysis,
Distributed Computing, Data Science.
Algorithmic spectral graph theory, distributed algorithms, data streaming
Graph Theory, Networks, and the application
of theoretical computer science to controlling the spread
of infectious disease.
Models of quantum computing and their structural relations,
exploring new applications, algorithms and cryptographic protocols
for quantum information processing devices.
current PhD Students
(now at University of Southern California)
Efficient algorithms for fundamental problems in machine
Santhanam (now at Oxford University)
Amin Coja-Oghlan (now at Frankfurt University)
Random structures and algorithms.
- Mark Jerrum
(now at QMUL)
Computational complexity, randomised algorithms, stochastic processes,
Previously graduated PhD Students
- Alistair Stewart (2015) Efficient algorithms for infinite-state
recursive stochastic models and Newton's method
- 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