See latex version here. See publication list here.


2022-NowPrincipal Researcher in Microsoft Research
2022-NowAssociate Professor in University of Washington
2017-2022Assistant Professor in University of Washington
2018-2022Visiting 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

2022Sampling with Riemannian Hamiltonian Monte Carlo in a Constrained Space (NeurIPS 2022)
Decomposable Non-Smooth Convex Optimization with Nearly-Linear Gradient Oracle Complexity (NeurIPS 2022)
A gradient sampling method with complexity guarantees for Lipschitz functions in high and low dimensions (NeurIPS 2022)
Differentially Private Fine-tuning of Language Models (NeurIPS 2022)
Private Convex Optimization via Exponential Mechanism (COLT 2022)
Faster maxflow via improved dynamic spectral vertex sparsifiers (STOC 2022)
Nested Dissection Meets IPMs: Planar Min-Cost Flow in Nearly-Linear Time (SODA 2022)
Computing Lewis Weights to High Precision (SODA 2022)
Differentially Private Fine-tuning of Language Models (ICLR 2022)
2021Numerical Composition of Differential Privacy (NeurIPS 2021)
Private Non-smooth ERM and SCO in Subquadratic Steps (NeurIPS 2021)
Lower Bounds on Metropolized Sampling Methods for Well-Conditioned Distributions (NeurIPS 2021)
Fast and Memory Efficient Differentially Private-SGD via JL Projections (NeurIPS 2021)
Reducing 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 421 Introduction to Algorithms
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)