Paul Beame

Computational complexity, proof complexity, and satisfiability.

Sham Kakade

Data science, optimization, statistics, machine learning.

Anna Karlin

Algorithms and algorithmic game theory

James R. Lee

Algorithms, complexity; functional analysis, probability, and metric geometry.

Yin Tat Lee

Convex optimization, algorithms [coming 2017!]

Shayan Oveis Gharan

Algorithms, spectral graph theory, applied probability.

Anup Rao

Complexity theory, communication complexity, information theory.

Thomas Rothvoss

Discrete optimization and linear/integer programming.

Sebastien Bubeck (MSR)

Machine learning, combinatorial statistics, stochastic and convex optimization.

Nikhil Devanur (MSR)

Fundamental algorithms and algorithmic game theory.

Maryam Fazel (UW EE)

Mathematical optimization, data analysis, and control theory.

Kamal Jain (Faira)

Developing new insights on commerce from a foundational perspective.

Sreeram Kannan (UW EE)

Information theory and computational biology.

Kostya Makarychev (MSR)

Approximation algorithms and combinatorial optimization.

Yuval Peres (MSR)

Probability. Random walks, percolation, mixing times, phase transitions, ergodic theory, game theory.

Mohit Singh (MSR)

Approximation algorithms, combinatorial optimization, and network design.

Rekha Thomas (UW Math)

Optimization and computational algebra.

Janardhan Kulkarni (MSR)

Algorithms

Miklos Z. Racz (MSR)

Probability theory and applications

**Fall 2017** Counting and Sampling (Oveis Gharan)

**Spring 2017** Algorithms and uncertainty (Devanur and Karlin)

**Autumn 2016** Randomized algorithms & probabilistic analysis (Lee)

**Spring 2016: ** Integer optimization and lattices (Rothvoss)

**Winter 2016: ** Entropy optimality (Lee)

**Autumn 2015: ** Communication Complexity (Rao)

**Spring 2015: ** Recent developments in approximation algorithms (Oveis Gharan)

**Theory reading group:** Convex optimization (Sp 2017)

**Related seminars:** CORE, Combinatorics, Probability

**Kira Goldner** is
named a Microsoft Research PhD Fellow.

The students of the UW theory group had an impressive
presence at SODA 2017. **Becca Hoberg** and **Thomas Rothvoss**
demonstrate A Logarithmic
Additive Integrality Gap for Bin Packing; **Cyrus Rashtchian**
and **Paul Beame** prove new results on Massively Parallel Similarity
Join, Edge-Isoperimetry, and Distance Correlations on the
Hypercube; **Alireza Rezaei** and **Shayan Oveis Gharan**
develop new Approximation
Algorithms for Finding Maximum Induced Expanders.

**Thomas Rothvoss** is named a Packard Fellow.

**Shayan Oveis Gharan** named one of the "10 Scientists to Watch" by Science News.

**Anna Karlin** elected to the American Academy of Arts & Sciences.

Amos Fiat, **Kira Goldner**, **Anna Karlin**, and Elias Koutsoupias characterize the optimal auction in the "FedEx setting", further demonstrating the importance of "ironing" and LP duality in mechanism design.

**Alireza Rezaei**, **Shayan**, and Nima Anari design efficient MCMC algorithms for sampling from homogeneous strongly Rayleigh measures, a generalization of k-determinantal point processes.

**Anup Rao** wins the 2016 *SIAM Outstanding Paper Prize* for his work with Boaz Barak, Mark Braverman and Xi Chen on how to compress interactive communication.

**Elaine Levey** and **Thomas** show how the Lasserre SDP hierarchy can be used to design
new approximation algorithms for the classical problem of min-makespan scheduling with precedence constraints.

Rong Ge, Qingqing Huang, and **Sham Kakade** design new efficient algorithms for
learning mixtures of Gaussians in high dimensions.

**Makrand Sinha** and **Anup** discover a simpler proof that information complexity
is not the same as communication complexity.

**Siva Ramamoorthy** and **Anup** give new techniques to compress communication protocols
when the amount of communication is asymmetric.

**James R. Lee**, Prasad Raghavendra, and David Steurer
win a *best paper award* at STOC 2015 for proving the
first super-polynomial lower bounds on semidefinite
extension complexity.

By proving a generalization of the Kadison-Singer conjecture,
**Shayan Oveis Gharan** and Nima Anari give an improved bound on the integrality gap of the classical Held-Karp relaxation for the Asymmetric Traveling Salesman Problem.

**Thomas Rothvoss** wins the *best paper award* at STOC 2014 for proving lower bounds
on the extension complexity of the matching polytope.
Lance Fortnow calls it the "complexity
result of the year."

Yuqing Ai

Algorithms, spectral graph theory, optimization

Jiechen Chen

Algorithmic game theory

Kira Goldner

Algorithmic game theory, probability, algorithms

Rebecca Hoberg

Algorithms, Linear and Integer Programming

Jeffrey Hon

Algorithms and complexity theory

Vincent Liew

Complexity, probability, quantum computing

Harish Ramadas

Optimization, probability

Siva Ramamoorthy

Complexity theory, communication complexity

Cyrus Rashtchian

Complexity theory, communication complexity, and analysis of Boolean functions

Alireza Rezaei

Approximation algorithms, spectral graph theory.

Mert Saglam

Computational complexity

Makrand Sinha

Communication complexity, circuit lower bounds, applications of information theory

Robbie Weber

Graph algorithms

Xin Yang

Complexity, hardness reduction, impossibility results