Computational complexity, proof complexity, and satisfiability

Data science, optimization, statistics, machine learning.

Algorithms and algorithmic game theory.

Algorithms, complexity, and optimization. Geometry and analysis at the interface between continuous and discrete.

Convex optimization, algorithms

Algorithms, spectral graph theory, applied probability.

Complexity theory, communication complexity, information theory.

Discrete optimization and linear/integer programming.

Machine learning, optimization, algorithms.

Machine learning, combinatorial statistics, stochastic and convex optimization.

Fundamental algorithms and algorithmic game theory.

Mathematical optimization, data analysis, and control theory.

Developing new insights on commerce from a foundational perspective.

Information theory and computational biology.

quantum algorithms and complexity theory

Algorithms

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

Algorithms for geometrically structured data.

Optimziation and compuational algebra

Error correcting codes, complexity theory, combinatorics

Algorithms, Linear and Integer Programming

Algorithms, big data processing

Algorithms, spectral graph theory, optimization

Approximation algorithms, probabilistic combinatorics

Algorithms, spectral graph theory

Algorithmic game theory, probability, algorithms

Algorithms and complexity theory

Complexity, probability, quantum computing

Convex optimization

Complexity theory, communication complexity

Complexity theory, communication complexity, and analysis of Boolean functions

Approximation algorithms, spectral graph theory

Computational complexity

Communication complexity, circuit lower bounds, applications of information theory

Graph algorithms

Complexity, hardness reductions, impossbility results

**
Spring
2018**
Competitive analysis via convex optimization
(Bubeck and J. Lee)

**
Winter
2018**
Interplay between convex optimization and geometry
(Y. T. Lee)

**
Winter
2018**
Student reading group
(lattices)

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

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

**
Fall
2016**
Randomized algorithms & probabilistic analysis
(J. Lee)

**
Spring
2016**
Integer Optimization and Lattices
(Rothvoss)

**
Winter
2016**
Entropy optimality
(J. Lee)

**
Fall
2015**
Communication complexity
(Rao)

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

**Yin Tat Lee** wins an NSF CAREER Award.

**James R. Lee** is named a Simons Investigator.

**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.”