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 staffMary CryanRandomized algorithms – especially for sampling and counting, learning theory, computational biologyHeng GuoTheoretical computer science – especially the complexity of counting problems for example, computing marginal probabilities and expectations of random variables, the evaluation of partition functionsKousha 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 theoryKyriakos KalorkotiComputational complexity, computer algebra, decision problems in group theoryRichard 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 gamesRik SarkarMachine learning algorithms, network analysis, computational geometry: topology, trajectory analysis, distributed computing, data scienceHe SunAlgorithmic spectral graph theory, distributed algorithms, data streaming algorithms External/Part-time AcademicsJessica EnrightGraph theory, networks, and the application of theoretical computer science to controlling the spread of infectious diseaseElham KashefiModels of quantum computing and their structural relations, exploring new applications, algorithms and cryptographic protocols for quantum information processing devicesCurrent PhD StudentsMaria AstefanoaeiRadu CiobanuVeselin BlagoevAbhirup GhoshEmanuel MartinovChrystalla PavlouBenedek Rozemberczki Previously Graduated PhD StudentsAlistair Stewart (2015)Efficient algorithms for infinite-state recursive stochastic models and Newton's methodhsdfhsdfhsdfhshshshsdfhsdhChiranjit Chakraborty (2014) Instance compression of parametric problems and related hierarchiesLorenzo Clemente (2012)Generalized simulation relations with applications in automata theoryPáidí Creed (2010) Counting and sampling problems on Eulerian graphsGrant Olney Passmore (2011) Combined decision procedures for nonlinear arithmetics, real and complexPast FacultyIlias DiakonikolasNow at University of Southern California. Efficient algorithms for fundamental problems in machine learningRahul Santhanam Now at Oxford University. Computational complexityAmin Coja-Oghlan Now at Frankfurt University. Random structures and algorithms.Mark JerrumNow at QMUL. Computational complexity, randomised algorithms, stochastic processes, random structures.Algorithmic Game TheoryComputational ComplexityRandomness and ComputationOld website This article was published on 2024-12-08
