See latex version here.


2017-NowAssistant Professor in University of Washington
2018-NowVisiting Researcher in Microsoft Research
2016-2017Postdoc in Microsoft Research


2012-2016Ph.D. in Mathematics, Massachusetts Institute of Technology
2008-2012B.S. in Mathematics, Chinese University of Hong Kong


2020Packard Fellowship
Sloan Research Fellowship
Best Student Paper by my PhD student Haotian Jiang, Symposium on Discrete Algorithms
2019Microsoft Research Faculty Fellowship
2018Best Paper Award, Neural Information Processing Systems
A. W. Tucker Prize
2016Sprowls Award, MIT
2015Best Student Paper, Symposium on Foundations of Computer Science
2014Notable article in computing in 2014 by Computing Reviews
Best Student Paper, Symposium on Foundations of Computer Science
Best Paper Award, Symposium on Foundations of Computer Science
Best Paper Award, Symposium on Discrete Algorithms
2013Charles W. and Jennifer C. Johnson Prize, MIT
2012MIT Presidential Fellowship

Selected Publications

2021A Nearly-Linear Time Algorithm for Linear Programs with Small Treewidth: A Multiscale Representation of Robust Central Path (STOC 2021)
2019Solving Linear Programs in the Current Matrix Multiplication Time (STOC 2019)
2018Optimal Algorithms for Non-Smooth Distributed Optimization in Networks (NeurIPS 2018)
k-server via multiscale entropic regularization (STOC 2018)
Convergence rate of Riemannian Hamiltonian Monte Carlo and faster polytope volume computation (STOC 2018)
2017Eldan's Stochastic Localization and the {KLS} Hyperplane Conjecture: An Improved Lower Bound for Expansion (FOCS 2017)
Kernel-based methods for bandit convex optimization (STOC 2017)
2015A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization (FOCS 2015)
2014Path Finding Methods for Linear Programming: Solving Linear Programs in $\tilde{O}(\sqrt{\mathrm{rank}})$ Iterations and Faster Algorithms for Maximum Flow (FOCS 2014)
An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations (SODA 2014)

Other Publications

2021Reducing Isotropy and Volume to KLS: An $O(n^3 \psi^2)$ Volume Algorithm (STOC 2021)
Minimum Cost Flows, MDPs, and l1-Regression in Nearly Linear Time for Dense Instances (STOC 2021)
2020Leverage Score Sampling for Faster Accelerated Regression and ERM (ALT 2020)
Logsmooth Gradient Concentration and Tighter Runtimes for Metropolized Hamiltonian Monte Carlo (COLT 2020)
An $O(m/\epsilon^{3.5})$-Cost Algorithm for Semidefinite Programs with Diagonal Constraints (COLT 2020)
A Faster Interior Point Method for Semidefinite Programming (FOCS 2020)
Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs (FOCS 2020)
Network size and size of the weights in memorization with two-layers neural networks (NeurIPS 2020)
Acceleration with a Ball Optimization Oracle (NeurIPS 2020)
Solving Tall Dense Linear Programs in Nearly Linear Time (STOC 2020)
An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games and its Applications (STOC 2020)
Strong Self-Concordance and Sampling (STOC 2020)
Computing Circle Packing Representations of Planar Graphs (SODA 2020)
Differentially Private Release of Synthetic Graphs (SODA 2020)
Chasing Nested Convex Bodies Nearly Optimally (SODA 2020)
A Generalized Central Limit Conjecture for Convex Bodies (GAFA Seminar Notes)
2019Complexity of Highly Parallel Non-Smooth Convex Optimization (NeurIPS 19)
The Randomized Midpoint Method for Log-Concave Sampling (NeurIPS 2019)
Faster Matroid Intersection (FOCS 2019)
Competitively chasing convex bodies (STOC 2019)
A near-optimal algorithm for approximating the John Ellipsoid (COLT 2019)
Near Optimal Methods for Minimizing Convex Functions with Lipschitz p-th Derivatives (COLT 2019)
Solving Empirical Risk Minimization in the Current Matrix Multiplication Time (COLT 2019)
Adversarial examples from computational constraints (ICML 2019)
Metrical task systems on trees via mirror descent and unfair gluing (SODA 2019)
A Nearly-Linear Bound for Chasing Nested Convex Bodies (SODA 2019)
2018Efficient Convex Optimization with Membership Oracles (COLT 2018)
Universal Barrier is n-Self-Concordant (arXiv)
The Kannan-Lovász-Simonovits Conjecture (arXiv)
The Paulsen problem, continuous operator scaling, and smoothed analysis (STOC 2018)
A matrix expander Chernoff bound (STOC 2018)
Stochastic localization + Stieltjes barrier = tight bound for log-Sobolev (STOC 2018)
An homotopy method for lp regression provably beyond self-concordance and in input-sparsity time (STOC 2018)
2017Optimal Algorithms for Smooth and Strongly Convex Distributed Optimization in Networks (ICML 2017)
An SDP-based algorithm for linear-sized spectral sparsification (STOC 2017)
Geodesic walks in polytopes (STOC 2017)
Subquadratic submodular function minimization (STOC 2017)
2016Faster Algorithms for Convex and Combinatorial Optimization ()
Black-box Optimization with a Politician (ICML 2016)
Using Optimization to Obtain a Width-Independent, Parallel, Simpler, and Faster Positive SDP Solver (SODA 2016)
Improved Cheeger's Inequality and Analysis of Local Graph Partitioning using Vertex Expansion and Expansion Profile (SODA 2016)
Geometric median in nearly linear time (STOC 2016)
Sparsified Cholesky and multigrid solvers for connection laplacians (STOC 2016)
Landmark-Matching Transformation with Large Deformation Via n-dimensional Quasi-conformal Maps (J. Sci. Comput.)
2015A geometric alternative to Nesterov's accelerated gradient descent (arXiv)
Efficient Inverse Maintenance and Faster Algorithms for Linear Programming (FOCS 2015)
Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time (FOCS 2015, SIAM J. Comput.)
Uniform Sampling for Matrix Approximation (ITCS 2015)
2014Single Pass Spectral Sparsification in Dynamic Streams (FOCS 2014, SIAM J. Comput.)
2013Efficient Accelerated Coordinate Descent Methods and Faster Algorithms for Solving Linear Systems (FOCS 2013)
Improved Cheeger's inequality: analysis of spectral partitioning algorithms (STOC 2013, SIAM J. Comput.)
A new approach to computing maximum flows using electrical flows (STOC 2013)


2020-2021CSE 535 Theory of Optimization and Continuous Algorithms
CSE 599 Sketching Algorithms
2019-2020CSE 535 Theory of Optimization and Continuous Algorithms
2018-2019CSE 535 Theory of Optimization and Continuous Algorithms
CSE 421 Introduction to Algorithms
2017-2018CSE 421 Introduction to Algorithms
CSE 599 Interplay between Convex Optimization and Geometry


2021Co-organizer of a workshop on “Continuous approaches to discrete optimization” at the Hausdorff Center for Mathematics
Local Organization Chair of APPROX & RANDOM 2021
Program Committee of Foundations of Computer Science (FOCS 2021)
2020Local Organization Chair of APPROX & RANDOM 2020
Program Committee of International Workshop on Randomization and Computation (RANDOM 2020)
2018Program Committee of Foundations of Computer Science (FOCS 2018)
2017Program Committee of Symposium on Discrete Algorithms (SODA 2017)
Co-organizer of a workshop in The 49th Annual ACM Symposium on the Theory of Computing (STOC 2017)
Program Committee of International Workshop on Randomization and Computation (RANDOM 2017)
2016Co-organizer of three sessions in The fifth International Conference on Continuous Optimization (ICCOPT 2016)