Theory talks:
[ earlier | later ] [ google calendar ] [ seminar recordings ]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
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
Machine learning, optimization, algorithms.
Machine learning, combinatorial statistics, stochastic and convex optimization.
Fundamental algorithms and algorithmic game theory.
Machine learning
Mathematical optimization, data analysis, and control theory.
Developing new insights on commerce from a foundational perspective.
Optimization, experimental design, machine learning
Information theory and computational biology.
quantum algorithms and complexity theory
Algorithms
Machine learning, security, and privacy
Algorithms for geometrically structured data.
Optimization and computational algebra
Error correcting codes, complexity theory, combinatorics
Seattle TCS postdocs
Cryptography
Graduate students
Algorithms, spectral graph theory
Machine learning, active learning
Cryptography, security
Algorithms, combinatorics
Algorithms, spectral graph theory
Cryptography, security, complexity theory
Algorithms and complexity theory
Information theory, combinatorics
Optimization, algorithms, convex geometry
Approximation algorithms, combinatorics
Stochastic optimization, algorithms
Algorithms, Markov chains, high-dimensional geometry
Cryptography, complexity theory
Convex optimization
Combinatorial and convex optimization
Algorithms, optimization
Cryptography
Complexity theory
Quantum computing, complexity, algorithms
Combinatorics, algorithms, quantum computing
Cryptography
Boolean function analysis, property testing, complexity
Cryptography, complexity theory
Approximation algorithms, geometry of polynomials
Alumni (PhD & Postdoc)
Algorithms, spectral graph theory, optimization
Approximation algorithms, probabilistic combinatorics
Mechanism design, approximation algorithms, algorithmic game theory
Algorithms, Linear and Integer Programming
Cryptography, security
Machine learning
Complexity, probability, quantum computing
Complexity theory, communication complexity
Complexity theory, communication complexity, and analysis of Boolean functions
Approximation algorithms, spectral graph theory
Computational complexity
Algorithms, spectral graph theory, optimization
Communication complexity, circuit lower bounds, applications of information theory
Algorithms, big data processing
Graph algorithms
Complexity, hardness reductions, impossbility results
Theory courses
SP 23 Randomized algorithms (S. Oveis Gharan)
WI 23 Analytic and geometric methods in TCS (J. R. Lee)
WI 23 Lattices (Rothvoss)
AU 22 Intro to Quantum Computing (J. R. Lee)
UW Theory highlights
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.
Yin Tat Lee is named a Packard Fellow.
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.
Shayan Oveis Gharan is named a 2019 Sloan Research Fellow.
Yin Tat Lee and coauthors win a best paper award at NeurIPS 2018 for their work on algorithms for distributed optimization.
Ewin Tang is one of the Forbes 30-under-30 in Science.
Yin Tat Lee wins the A. W. Tucker Prize for his thesis Faster Algorithms for Convex and Combinatorial Optimization.
Thomas Rothvoss wins the Fulkerson Prize for his work on the perfect matching polytope.
Yin Tat Lee wins an NSF CAREER Award.
James R. Lee is named a Simons Investigator.
Shayan Oveis Gharan is named an ONR Young 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.”