Efficient Convex Optimization Requires Superlinear Memory
With Annie Marsden, Vatsal Sharan, and Gregory Valiant
Conference on Learning Theory (COLT 2022)
Best paper award (arXiv)
Acceleration with a Ball Optimization Oracle
With Yair Carmon, Arun Jambulapati, Qijia Jiang, Yujia Jin, Yin Tat Lee, and Kevin Tian
In Conference on Neural Information Processing Systems (NeurIPS 2020)
Oral presentation (arXiv)
Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs
With Jan van den Brand, Yin Tat Lee, Danupon Nanongkai, Richard Peng, Thatchaphol Saranurak, Zhao Song, and Di Wang
In Symposium on Foundations of Computer Science (FOCS 2020)
Invited to the special issue (arXiv)
Unit Capacity Maxflow in Almost $O(m^{4/3})$ Time
With Tarun Kathuria and Yang P. Liu
In Symposium on Foundations of Computer Science (FOCS 2020)
Invited to the special issue (arXiv before merge))
Solving Tall Dense Linear Programs in Nearly Linear Time
With Jan van den Brand, Yin Tat Lee, and Zhao Song
In Symposium on Theory of Computing (STOC 2020)
Invited to the special issue (arXiv)
Complexity of Highly Parallel Non-Smooth Convex Optimization
With Sébastien Bubeck, Qijia Jiang, Yin Tat Lee, and Yuanzhi Li
In Conference on Neural Information Processing Systems (NeurIPS 2019)
Spotlight presentation (arXiv)
Principal Component Projection and Regression in Nearly Linear Time through Asymmetric SVRG
With Yujia Jin
In Conference on Neural Information Processing Systems (NeurIPS 2019)
Spotlight presentation (arXiv)
Deterministic Approximation of Random Walks in Small Space
With Jack Murtagh, Omer Reingold, and Salil P. Vadhan
In International Workshop on Randomization and Computation (RANDOM 2019)
Invited to the special issue (arXiv)
Coordinate Methods for Accelerating ℓ∞ Regression and Faster Approximate Maximum Flow
With Kevin Tian
In Symposium on Foundations of Computer Science (FOCS 2018)
Invited to the special issue (arXiv)
Almost-Linear-Time Algorithms for Markov Chains and New Spectral Primitives for Directed Graphs
With Michael B. Cohen, Jonathan A. Kelner, John Peebles, Richard Peng, Anup B. Rao, and, Adrian Vladu
In Symposium on Theory of Computing (STOC 2017)
Invited to the special issue (arXiv)
A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization
With Yin Tat Lee and Sam Chiu-wai Wong
In Symposium on Foundations of Computer Science (FOCS 2015)
Machtey Award for Best Student Paper (arXiv)
Path-Finding Methods for Linear Programming : Solving Linear Programs in Õ(√rank) Iterations and Faster Algorithms for Maximum Flow
With Yin Tat Lee
In Symposium on Foundations of Computer Science (FOCS 2014)
Best Paper Award and Machtey Award for Best Student Paper (arXiv)
Single Pass Spectral Sparsification in Dynamic Streams
With Michael Kapralov, Yin Tat Lee, Cameron Musco, and Christopher Musco
In Symposium on Foundations of Computer Science (FOCS 2014)
Invited to the special issue (arXiv)
An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations
With Jonathan A. Kelner, Yin Tat Lee, and Lorenzo Orecchia
In Symposium on Discrete Algorithms (SODA 2014)
Best paper award (arXiv)