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