Professors Yin Tat Lee and Thomas Rothvoss are faculty at the Allen School of the University of Washington.
Lee has the A.W. Tucker Prize that recognizes the best doctoral thesis in optimization in the past three years. Rothvoss, who holds a dual appointment in the Allen School and the Department of Mathematics, earned the Delbert Ray Fulkerson Prize recognizing outstanding papers in the area of discrete mathematics. They are advising theory PhD students in the Allen School—some jointly.
Paul Beame and Anna Karlin are some of the top senior theorists in the Allen School that I have known for many years.
Sally
One of the students in the theory group is Sally Dong who is a final year PhD student. I ran across her work recently the other day
here. She is working with Lee and Rothvoss. 
Sally’s Paper
Computing Circle Packing Representations of Planar Graphs by Sally Dong, Yin Tat Lee, Kent Quanrud. See it here:
The Circle Packing Theorem states that every planar graph can be represented as the tangency graph of a family of internally-disjoint circles. A well-known generalization is the Primal-Dual Circle Packing Theorem for 3-connected planar graphs. The existence of these representations has widespread applications in theoretical computer science and mathematics; however, the algorithmic aspect has received relatively little attention. In this work, we present an algorithm based on convex optimization for computing a primal-dual circle packing representation of maximal planar graphs, i.e. triangulations. This in turn gives an algorithm for computing a circle packing representation of any planar graph. Both take the O(nlog(R/s)) expected run-time to produce a solution that is s close to a true representation, where R is the ratio between the maximum and minimum circle radius in the true representation.
Open Problems
I loved the fact that the Circle Packing Theorem was related to an ancient theorem of mine—with Bob Tarjan—on planar graphs. Dong’s paper says:
It gives a geometric proof of the Planar Separator Theorem of Lipton and Tarjan; an analysis of circle packing properties further gives an improved constant bound for the separator size; it is also used crucially to design a simple spectral algorithm for computing optimal separators in graphs of bounded genus and degree.
I loved that it could be used to prove better bounds on the size of the separators. Very cool.
Related
