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.

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

Debmalya Panigrahi | debm...@alum.mit.edu

Theory of Algorithms: graph algorithms (particularly graph connectivity and network design), resource allocation, online and approximation algorithms, combinatorial optimization.
Applied Algorithms: Algorithmic problems in social, information, and communication networks, distributed systems, databases, etc.

Roy Schwartz | roy...@microsoft.com

Design and analysis of algorithms, Approximation algorithms, Metric methods and their algorithmic applications, Submodular optimization, Randomized algorithms

UW Theory Postdocs

Xin Li | lixi...@cs.washington.edu

Randomness in computation, Complexity theory, Distributed computing, Cryptography.

Pavel HrubeŠ | pahr...@gmail.com

Proof Complexity, Arithmetic Circuit Complexity, Mathematical logic.

UW Theory Students

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.

Alexander Jaffe | aja...@cs.washington.edu

Advised by: James Lee

Metric embeddings, approximation algorithms, structural graph theory, convex optimization, learning theory.

Paraschos Koutris | pkou...@cs.washington.edu

Advised by: Dan Suciu

Database Theory, Data pricing, Theoretical parallel models for MapReduce-like frameworks

Widad Machmouchi | wid...@cs.washington.edu

Advised by: Paul Beame

Coding theory, Time Space tradeoffs, Pseudorandomness, and Complexity Theory in general.

Mohammad Moharrami | moh...@cs.washington.edu

Advised by: James Lee

Combinatorial optimization, metric embedding, and approximation algorithms.

Daniel Poore |

Advised by: James Lee

Cyrus Rashtchian | cyr...@cs.washington.edu

Advised by: James Lee

Interests: Spectral graph theory, structural graph theory, algorithm design, stochastic optimization, machine learning.

Makrand Sinha | mak...@cs.washington.edu

Advised by: Anup Rao

Interests: Complexity theory (Circuit lower bounds, Average-case complexity, Pseudorandomness, Communication Complexity) and Metric Embeddings.

Kevin Zatloukal | kev...@cs.washington.edu

Advised by: Aram Harrow

Quantum computing, Algorithms.

David Rosenbaum | djr...@cs.washington.edu

Advised by: Paul Beame and Aram Harrow

Algorithms (both classical and quantum), group isomorphism, algebraic problems, alternate oracle models, query complexity, state preparation, symmetrization and quantum circuits.