CS Theory @ UW

Theory   |   CSE   |   MSR ALG   |   MSR ML+O   |   Courses   |   News
Theory   |   CSE   |   Courses   |   News  

Theory talks:

  [ earlier | later ]   [ google calendar ]

Faculty

Paul Beame

Computational complexity, proof complexity, and satisfiability

Kevin Jamieson

Optimization, experimental design, machine learning

Sham Kakade

Data science, optimization, statistics, machine learning

Anna Karlin

Algorithms and algorithmic game theory

James R. Lee

Algorithms, complexity, optimization, probability

Yin Tat Lee

Convex optimization, algorithms

Huijia (Rachel) Lin

Cryptography, security, complexity theory

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

Stefano Tessaro

Cryptography and security

Affiliated Researchers

Zeyuan Allen-Zhu (MSR)

Machine learning, optimization, algorithms.

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.

Robin Kothari (MSR)

quantum algorithms and complexity theory

Janardhan Kulkarni (MSR)

Algorithms

Ilya Razenshteyn (MSR)

Algorithms for geometrically structured data.

Rekha Thomas (UW Math)

Optimziation and compuational algebra

Sergey Yekhanin (MSR)

Error correcting codes, complexity theory, combinatorics

Seattle TCS postdocs

Becca Hoberg (UW Math)

Algorithms, Linear and Integer Programming

Lalit Jain

Machine learning

Xiaorui Sun (MSR)

Algorithms, big data processing

Graduate students

Yuqing Ai

Algorithms, spectral graph theory, optimization

Sami Davies

Approximation algorithms, probabilistic combinatorics

Sally Dong

Algorithms, combinatorics

Farzam Ebrahimnejad

Algorithms, spectral graph theory

Kira Goldner

Mechanism design, approximation algorithms, algorithmic game theory

Jeffrey Hon

Algorithms and complexity theory

Siddharth Iyer

Information theory, combinatorics

Haotian Jiang

Optimization, algorithms, convex geometry

Nathan Klein

Approximation algorithms, combinatorics

Vincent Liew

Complexity, probability, quantum computing

Kuikui Liu

Algorithms, geometry of polynomials, spectral graph theory

Swati Padmanabhan

Convex optimization

Siva Ramamoorthy

Complexity theory, communication complexity

Victor Reis

Combinatorial and convex optimization

Alireza Rezaei

Approximation algorithms, spectral graph theory

Jennifer Rogers

Machine learning, active learning

Mert Saglam

Computational complexity

Ruoqi Shen

Algorithms, optimization

Oscar Sprumont

Complexity theory

Ewin Tang

Combinatorics, algorithms, quantum computing

Robbie Weber

Graph algorithms

Xin Yang

Complexity, hardness reductions, impossbility results

Alumni

Cyrus Rashtchian

Complexity theory, communication complexity, and analysis of Boolean functions

Makrand Sinha

Communication complexity, circuit lower bounds, applications of information theory

Theory courses

SP 19 Cryptography (Lin)

SP 19 Randomized algorithms (J. Lee)

SP 19 Communication complexity and lower bounds (A. Rao)

WI 19 Probabilistic combinatorics (T. Rothvoss)

WI 19 Theory of convex optimization (Y. T. Lee)

AU 18 Algorithms through a geometric lens (Razenshteyn)

SP 18 Competitive analysis via convex optimization (Bubeck and J. Lee)

WI 18 Interplay between convex optimization and geometry (Y. T. Lee)

UW Theory highlights

Yin Tat Lee and coauthors win a best paper award at NeurIPS 2018 for their work on algorithms for distributed optimization.

Thomas Rothvoss wins the Fulkerson Prize for his work on the perfect matching polytope.

Shayan Oveis Gharan is named an ONR Young Investigator.

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.

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.

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