CS Theory @ UW

CS Theory @ UW

Theory   |   CSE   |   Courses   |   Papers   |   News  

Theory talks:

  [ earlier | later ]   [ google calendar ]   [ seminar recordings ]

Theory talks:

  [ earlier | later ]   [ google calendar ]   [ seminar recordings ]

Faculty

Faculty

Computational complexity, proof complexity, and satisfiability

Quantum computation and cryptography

Algorithms and algorithmic game theory

Algorithms, complexity, optimization, probability

Convex optimization, algorithms

Cryptography, security, complexity theory

Machine learning, algorithmic game theory

Quantum information and hardness of approximation

Algorithms, spectral graph theory, applied probability

Complexity theory, communication complexity, information theory

Discrete optimization and linear/integer programming

Cryptography, security, complexity theory, information theory

Graph algorithms

Affiliated Researchers

Affiliated Researchers

Machine learning, optimization, algorithms.

Machine learning, combinatorial statistics, stochastic and convex optimization.

Nikhil Devanur (Amazon)
Nikhil Devanur (Amazon)

Fundamental algorithms and algorithmic game theory.

Machine learning

Maryam Fazel (UW EE)
Maryam Fazel (UW EE)

Mathematical optimization, data analysis, and control theory.

Kamal Jain (Faira)
Kamal Jain (Faira)

Developing new insights on commerce from a foundational perspective.

Optimization, experimental design, machine learning

Sreeram Kannan (UW EE)
Sreeram Kannan (UW EE)

Information theory and computational biology.

quantum algorithms and complexity theory

Algorithms

Machine learning, security, and privacy

Algorithms for geometrically structured data.

Rekha Thomas (UW Math)
Rekha Thomas (UW Math)

Optimization and computational algebra

Error correcting codes, complexity theory, combinatorics

Seattle TCS postdocs

Seattle TCS postdocs

Continuous optimization, high-dimensional probability, and graph algorithms

Graduate students

Graduate students

Dorna Abdolazimi
Dorna Abdolazimi

Algorithms, spectral graph theory

Algorithms, combinatorics

Algorithms, spectral graph theory

Cryptography, security, complexity theory

Information theory, combinatorics

Approximation algorithms, combinatorics

Daogao Liu
Daogao Liu

Stochastic optimization, algorithms

Cryptography, complexity theory

Convex optimization

Combinatorial and convex optimization

Algorithms, optimization

Cryptography

Oscar Sprumont
Oscar Sprumont

Complexity theory

Artin Tajdini
Artin Tajdini

Quantum computing, complexity, algorithms

Combinatorics, algorithms, quantum computing

Ben Terner
Ben Terner

Cryptography

Boolean function analysis, property testing, complexity

Xihu Zhang
Xihu Zhang

Cryptography, complexity theory

Xinzhi Zhang
Xinzhi Zhang

Approximation algorithms, geometry of polynomials

Alumni (PhD & Postdoc)

Alumni (PhD & Postdoc)

Yuqing Ai
Yuqing Ai

Algorithms, spectral graph theory, optimization

Machine learning, active learning

Cryptography, security

Approximation algorithms, probabilistic combinatorics

Mechanism design, approximation algorithms, algorithmic game theory

Becca Hoberg (UW Math)
Becca Hoberg (UW Math)

Algorithms, Linear and Integer Programming

Algorithms and complexity theory

Cryptography, security

Machine learning

Optimization, algorithms, convex geometry

Complexity, probability, quantum computing

Algorithms, Markov chains, high-dimensional geometry

Cryptography

Complexity theory, communication complexity

Complexity theory, communication complexity, and analysis of Boolean functions

Alireza Rezaei
Alireza Rezaei

Approximation algorithms, spectral graph theory

Computational complexity

Algorithms, spectral graph theory, optimization

Communication complexity, circuit lower bounds, applications of information theory

Xiaorui Sun (MSR)
Xiaorui Sun (MSR)

Algorithms, big data processing

Graph algorithms

Complexity, hardness reductions, impossbility results

Theory   |   Crypto   |   CSE   |   MSR (ALG,   ML+O )   |   Courses   |   Papers   |   News

Theory courses

AU 23 Sparsification, sampling, and optimization (J. R. Lee)

SP 23 Randomized algorithms (S. Oveis Gharan)

Recent eprints

2023-09-11 Textbooks Are All You Need II: phi-1.5 technical report. Yuanzhi Li, Sébastien Bubeck, Ronen Eldan, Allie Del Giorno, Suriya Gunasekar, and Yin Tat Lee.
2023-08-28 Faster Min-Cost Flow on Bounded Treewidth Graphs. Sally Dong and Guanghao Ye.
2023-08-18 Do you know what q-means?. João F. Doriguello, Alessandro Luongo, and Ewin Tang.
2023-08-13 Snowblind: A Threshold Blind Signature in Pairing-Free Groups. Elizabeth Crites, Chelsea Komlo, Mary Maller, Stefano Tessaro, and Chenzhi Zhu.
2023-08-11 A Better-Than-1.6-Approximation for Prize-Collecting TSP. Jannis Blauth, Nathan Klein, and Martin Nägele.
2023-08-02 Optimal Online Discrepancy Minimization. Janardhan Kulkarni, Victor Reis, and Thomas Rothvoss.
2023-07-07 Scalable Membership Inference Attacks via Quantile Regression. Martin Bertran, Shuai Tang, Michael Kearns, Jamie Morgenstern, Aaron Roth, and Zhiwei Steven Wu.
2023-06-20 Textbooks Are All You Need. Suriya Gunasekar, Yi Zhang, Jyoti Aneja, Caio César Teodoro Mendes, Allie Del Giorno, Sivakanth Gopi, Mojan Javaheripi, Piero Kauffmann, Gustavo de Rosa, Olli Saarikivi, Adil Salim, Shital Shah, Harkirat Singh Behl, Xin Wang, Sébastien Bubeck, Ronen Eldan, Adam Tauman Kalai, Yin Tat Lee, and Yuanzhi Li.
2023-06-13 Integrated Simulation Platform for Quantifying the Traffic-Induced Environmental and Health Impacts. Xuanpeng Zhao, Guoyuan Wu, Akula Venkatram, Ji Luo, Peng Hao, Kanok Boriboonsomsin, and Shaohua Hu.

UW Theory highlights

Thomas Rothvoss shares the 2023 Gödel Prize for his work on the extension complexity of the matching polytope.

Rachel Lin named one of the “10 Scientists to Watch” by Science News.

Shayan Oveis Gharan is named a Simons Investigator.

Shayan Oveis Gharan wins 2021 Presburger Award for Young Scientists from EATCS for his research on TSP.

Paul Beame is recognized with an ACM SIGACT Distinguished Service Award.

Anna Karlin and collaborators win the ACM Paris Kanellakis Theory and Practice Award for their work on the power of two choices.

Anna Karlin is elected to the National Academy of Sciences.

Anna Karlin, Nathan Klein, and Shayan Oveis Gharan win a best paper award at STOC 2021 for their work A (Slightly) Improved Approximation Algorithm for Metric TSP.

Rachel Lin and coauthors achieve `Crown Jewel’ of Cryptography for their work on Indistinguishability Obfuscation from Well-Founded Assumptions, and receive a best paper award at STOC 2021.

Haotian Jiang wins a best student paper award at SODA 2021 for his work on minimizing convex functions with integral minimizers.

Anup Rao and Amir Yehudayoff publish Communication Complexity and Applications, a modern take on this foundational topic.

Kuikui Liu, Shayan Oveis Gharan and coauthors win a best paper award at STOC 2019 for their work on counting bases of matroids.

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