Sebastien Bubeck
(MSR)

Sebastien Bubeck
(MSR)

Machine learning, combinatorial statistics, stochastic and convex optimization.

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.

Sergey Yekhanin
(MSR)

Sergey Yekhanin
(MSR)

Error correcting codes, complexity theory, combinatorics

Dorna Abdolazimi

Dorna Abdolazimi

Algorithms, spectral graph theory

Oscar Sprumont

Oscar Sprumont

Complexity theory

Artin Tajdini

Artin Tajdini

Quantum computing, complexity, algorithms

Xinzhi Zhang

Xinzhi Zhang

Approximation algorithms, geometry of polynomials

Yuqing Ai

Yuqing Ai

Algorithms, spectral graph theory, optimization

Continuous optimization, high-dimensional probability, and graph algorithms

Complexity theory, communication complexity, and analysis of Boolean functions

Alireza Rezaei

Alireza Rezaei

Approximation algorithms, spectral graph theory

Communication complexity, circuit lower bounds, applications of information theory

Ben Terner

Ben Terner

Cryptography

Xihu Zhang

Xihu Zhang

Cryptography, complexity theory

**
SP
24**
Exponential-Time Hypotheses, Fine-Grained Complexity, and Lifting
(P. Beame)

**
WI
24**
Open problems in communication complexity
(A. Rao)

2024-05-19
Information-Theoretic Multi-Server PIR with Global Preprocessing.
Ashrujit Ghoshal, Baitian Li, Yaohua Ma, Chenxin Dai, and Elaine Shi.

2024-05-13
Who's in and who's out? A case study of multimodal CLIP-filtering in
DataComp.
Rachel Hong, William Agnew, Tadayoshi Kohno, and Jamie Morgenstern.

2024-05-10
A computational test of quantum contextuality, and even simpler proofs
of quantumness.
Atul Singh Arora, Kishor Bharti, Alexandru Cojocaru, and Andrea Coladangelo.

2024-04-30
Structure learning of Hamiltonians from real-time evolution.
Ainesh Bakshi, Allen Liu, Ankur Moitra, and Ewin Tang.

2024-04-22
Phi-3 Technical Report: A Highly Capable Language Model Locally on Your
Phone.
Marah Abdin, Sam Ade Jacobs, Ammar Ahmad Awan, Jyoti Aneja, Ahmed Awadallah, Hany Awadalla, Nguyen Bach, Amit Bahree, Arash Bakhtiari, Harkirat Behl, ....

2024-04-16
On approximability of the Permanent of PSD matrices.
Farzam Ebrahimnejad, Ansh Nagda, and Shayan Oveis Gharan.

2024-04-04
The power of a single Haar random state: constructing and separating
quantum pseudorandomness.
Boyang Chen, Andrea Coladangelo, and Or Sattath.

2024-03-28
Improving the Bit Complexity of Communication for Distributed Convex
Optimization.
Mehrdad Ghadiri, Yin Tat Lee, Swati Padmanabhan, William Swartworth, David Woodruff, and Guanghao Ye.

2024-03-25
High-Temperature Gibbs States are Unentangled and Efficiently Preparable.
Ainesh Bakshi, Allen Liu, Ankur Moitra, and Ewin Tang.

**Victor Reis** and **Thomas Rothvoss** are awarded a FOCS 2023 best paper award for their work on
The subspace flatness conjecture and faster integer programming.

**Paul Beame**, Paris Koutris, and Dan Suciu receive the 2023 ACM PODS Test-of-Time Award for their work on parallel database query processing.

**Shayan Oveis Gharan** receives the 2023 Stephen Smale Prize for his work on algebraic and spectral methods
in algorithm design.

Dadush, Eisenbrand, and **Rothvoss** win the IPCO 2023 best paper award for
their work From approximate to exact integer programming

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

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