UW Theory Faculty

Paul Beame | bea...@cs.washington.edu

Computational complexity, primarily proving lower bounds on the resources needed for solving computational problems. Communication complexity, time-space tradeoff lower bounds, proof complexity, formal reasoning and verification.

Aram Harrow | a.ha...@bris.ac.uk

The interplay between physics, mathematics and theoretical computer science. My current research is on quantum algorithms and quantum information theory, with an emphasis on finding new uses of symmetry, pseudorandomness and entanglement.

Anna Karlin | kar...@cs.washington.edu

Design and analysis of algorithms, particularly probabilistic and online algorithms. The interface between theory and other areas, such as economics and game theory, data mining, operating systems, networks, and distributed systems.

Richard Ladner | lad...@cs.washington.edu

Data compression, cache performance of algorithms, algorithms for media-on-demand systems.

James R. Lee | jrl...@cs.washington.edu

Algorithms, complexity, optimization. High-dimensional geometry, geometry of discrete metric spaces, spectral graph theory. Applications of geometry and analysis in theoretical computer science.

Anup Rao | an...@cs.washington.edu

Pseudorandomness, Complexity, Coding Theory, Combinatorics.

MSR Permanent Members

Nikhil R. Devanur | nik...@microsoft.com

Fundamental algorithmic problems such as graph partitioning and network design. Algorithmic challenges in economics and game theory, such as computing market equilibrium and auction design.

Alexander E. Holroyd | hol...@microsoft.com

Discrete spatial models, including cellular automata, percolation, matching, coupling.

Kostantin Makarychev | ...

Approximation algorithms, combinatorial optimization, and semidefinite programming

Mohit Singh | moh...@microsoft.com

Approximation Algorithms, Combinatorial Optimization with applications in network design. Also interested in models and problems dealing with uncertainty in data.

Eyal Lubetzky | eya...@microsoft.com

Probabilistic methods in combinatorics, random graph models and processes, random walks, mixing times of Markov chains.

Yuval Peres | per...@microsoft.com

Random walks on graphs, Markov chains and randomized algorithms, game theory, decision tree complexity, information theory, metric embeddings, constrained optimization.

David B. Wilson | dav...@microsoft.com

Statistical physics, dimers, SLE, Markov chain mixing times, randomized algorithms.

MSR Postdocs

Shaddin Dughmi

Algorithms, combinatorial optimization, game theory, mechanism design.

Jason Miller | ...@microsoft.com

All forms of probability theory, with a focus on stochastic interface models such as random surfaces and SLE.

Alexandre Stauffer

Random walks, percolation, interacting particle systems, mixing time of Markov chains, randomized algorithms.

Sabbatical visitors

Manor Mendel | Open University, Israel

Geometry of discrete metric spaces, and algorithms that use metric data.

Bruce Shepherd | McGill University

Optimization, especially combinatorial optimization and graph theory. His recent work has focused on robust optimization of networks and the disjoint paths problem.

UW Theory Students

Ben Birnbaum | bir...@cs.washington.edu

Advised by: Anna Karlin

Online algorithms, approximation algorithms, and algorithmic game theory.

L. Elisa Celis | ece...@cs.washington.edu

Advised by: Anna Karlin and Yuval Peres

Applications of probabilistic methods in theoretical computer science and game theory. Markov chain mixing times, cooperative game theory, randomized algorithms, online algorithms, random walks.

Jessica Chang | jsc...@cs.washington.edu

Advised by: Anna Karlin

Algorithmic game theory, online algorithms.

Dimitrios Gklezakos | gkl...@cs.washington.edu

Advised by: Anna Karlin

My primary interests include Algorithmic Game Theory (especially auctions), Randomized Algorithms and Computational Complexity. Some of my additional interests include Evolutionary Game Theory and Combinatorics. Lately I am working on the Matroid Secretary problem which is an extension of the classic secretary problem to matroid settings. I am working with professor Anna Karlin and post-doc Shaddin Dughmi.