Selected Publications

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)