Publications

    2026
  1. Fast Convergence of Gradient Descent on Random ℓp-Norm Regression
    Yang P. Liu, Richard Peng, Weina Wang, Junzhao Yang
    FOCS 2026
  2. Approximate Spanning Tree Counting from Uncorrelated Edge Sets
    Yang P. Liu, Richard Peng, Junzhao Yang
    FOCS 2026
    arXiv
  3. Improved Parallel Repetition for GHZ-Supported Games via Spreadness
    Yang P. Liu, Shachar Lovett, Kunal Mittal
    CCC 2026
    arXiv
  4. Streaming Complexity Separations for Dense and Sparse Graphs
    Yang P. Liu, Hoai-An Nguyen, Noah G. Singer, David P. Woodruff
    ICALP 2026
    arXiv
  5. Adaptive Matrix Sparsification and Applications to Empirical Risk Minimization
    Yang P. Liu, Richard Peng, Colin Tang, Albert Weng, Junzhao Yang
    Manuscript
    arXiv
  6. An Analytical Approach to Parallel Repetition via CSP Inverse Theorems
    Amey Bhangale, Mark Braverman, Subhash Khot, Yang P. Liu, Dor Minzer, Kunal Mittal
    STOC 2026
    arXiv
  7. Incremental Shortest Paths in Almost Linear Time via a Modified Interior Point Method
    Yang P. Liu
    STOC 2026
    arXiv
  8. Sparsifying Sums of Positive Semidefinite Matrices
    Arpon Basu, Pravesh K. Kothari, Yang P. Liu, Raghu Meka
    SODA 2026
    arXiv
    9. 2025
  9. Quasipolynomial bounds for the corners theorem
    Michael Jaber, Yang P. Liu, Shachar Lovett, Anthony Ostuni, Mehtaab Sawhney
    FOCS 2025, Best Paper
    arXiv
  10. On Inverse Theorems and Combinatorial Lines
    Amey Bhangale, Subhash Khot, Yang P. Liu, Dor Minzer
    FOCS 2025
    Merged version of CSPs VI, CSPs VII, and DHJ[3] papers below.
  11. Parallel Repetition for 3-Player XOR Games
    Amey Bhangale, Mark Braverman, Subhash Khot, Yang P. Liu, Dor Minzer
    STOC 2025
    arXiv
  12. Reasonable Bounds for Combinatorial Lines of Length Three
    Amey Bhangale, Subhash Khot, Yang P. Liu, Dor Minzer
    Merged version accepted to FOCS 2025
    arXiv
  13. On Approximability of Satisfiable k-CSPs: VII
    Amey Bhangale, Subhash Khot, Yang P. Liu, Dor Minzer
    Merged version accepted to FOCS 2025
    arXiv
  14. On Approximability of Satisfiable k-CSPs: VI
    Amey Bhangale, Subhash Khot, Yang P. Liu, Dor Minzer
    Merged version accepted to FOCS 2025
    arXiv
    15. 2024
  15. On Approximate Fully-Dynamic Matching and Online Matrix-Vector Multiplication
    Yang P. Liu
    FOCS 2024
    arXiv
  16. Almost-Linear Time Algorithms for Decremental Graphs: Min-Cost Flow and More via Duality
    Jan van den Brand, Li Chen, Rasmus Kyng, Yang P. Liu, Simon Meierhans, Maximilian Probst Gutenberg, Sushant Sachdeva
    FOCS 2024
    arXiv
  17. Parallel Repetition for k-Player Projection Games
    Amey Bhangale, Mark Braverman, Subhash Khot, Yang P. Liu, Dor Minzer
    RANDOM 2024
    Proceedings      arXiv      Slides
  18. On Further Questions Regarding Unit Fractions
    Yang P. Liu, Mehtaab Sawhney
    In submission
    arXiv
  19. Sparsifying generalized linear models
    Arun Jambulapati, James R. Lee, Yang P. Liu, Aaron Sidford
    STOC 2024
    Proceedings      arXiv      Slides      Video
  20. Almost-Linear Time Algorithms for Incremental Graphs: Cycle Detection, SCCs, s-t Shortest Path, and Minimum-Cost Flow
    Li Chen, Rasmus Kyng, Yang P. Liu , Simon Meierhans, Maximilian Probst Gutenberg.
    STOC 2024
    Proceedings      arXiv
  21. Incremental Approximate Maximum Flow on Undirected Graphs in Subpolynomial Update Time
    Jan van den Brand, Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, Sushant Sachdeva, Aaron Sidford.
    SODA 2024
    Proceedings      arXiv
    22. 2023
  22. A Deterministic Almost-Linear Time Algorithm for Minimum-Cost Flow
    Jan van den Brand, Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, Sushant Sachdeva, Aaron Sidford
    FOCS 2023
    Proceedings      arXiv
  23. Sparsifying Sums of Norms
    Arun Jambulapati, James R. Lee, Yang P. Liu, Aaron Sidford
    FOCS 2023, Invited to SICOMP Special Issue
    Proceedings      arXiv
  24. Chaining, Group Leverage Score Overestimates, and Fast Spectral Hypergraph Sparsification
    Arun Jambulapati, Yang P. Liu, Aaron Sidford
    STOC 2023
    Proceedings      arXiv
  25. Dynamic Maxflow via Dynamic Interior Point Methods
    Jan van den Brand, Yang P. Liu, Aaron Sidford
    STOC 2023
    Proceedings      arXiv
  26. Vertex Sparsification for Edge Connectivity in Polynomial Time
    Yang P. Liu
    ITCS 2023
    Proceedings      arXiv
  27. Exponential Convergence of Sinkhorn Under Regularization Scheduling
    Jingbang Chen, Yang P. Liu, Richard Peng, Arvind Ramaswami
    ACDA 2023
    Proceedings      arXiv
    28. 2022
  28. Optimal Sublinear Sampling of Spanning Trees and Determinantal Point Processes via Average-Case Entropic Independence
    Nima Anari, Yang P. Liu, Thuy-Duong Vuong
    FOCS 2022, SIAM Journal of Computing Special Issue
    Journal      Proceedings      arXiv
  29. Maximum Flow and Minimum-Cost Flow in Almost Linear Time
    Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, Sushant Sachdeva
    FOCS 2022, Best Paper, Journal of the ACM
    Proceedings      arXiv      Slides      Video
  30. Online Edge Coloring via Tree Recurrences and Correlation Decay
    Janardhan Kulkarni, Yang P. Liu, Ashwin Sah, Mehtaab Sawhney, Jakub Tarnawski
    STOC 2022, SIAM Journal of Computing Special Issue
    Journal      Proceedings      arXiv
  31. Improved Iteration Complexities for Overconstrained p-Norm Regression
    Arun Jambulapati, Yang P. Liu, Aaron Sidford
    STOC 2022
    Proceedings      arXiv
  32. Faster Maxflow via Improved Dynamic Spectral Vertex Sparsifiers
    Jan van den Brand, Yu Gao, Arun Jambulapati, Yin Tat Lee, Yang P. Liu, Richard Peng, Aaron Sidford
    STOC 2022
    Proceedings      arXiv
  33. A Gaussian Fixed Point Walk
    Yang P. Liu, Ashwin Sah, Mehtaab Sawhney
    ITCS 2022, Best Student Paper
    Proceedings      arXiv      Slides      Video
  34. Arithmetic progressions in sumsets of sparse sets
    Noga Alon, Ryan Alweiss, Yang P. Liu, Anders Martinsson, Shyam Narayanan
    Integers
    Journal      arXiv
    35. 2021
  35. Fully Dynamic Electrical Flows: Sparse Maxflow Faster Than Goldberg-Rao
    Yu Gao, Yang P. Liu, Richard Peng
    FOCS 2021, SIAM Journal of Computing Special Issue
    Journal      Proceedings      arXiv      Slides      Video
  36. Minor Sparsifiers and the Distributed Laplacian Paradigm
    Sebastian Forster, Gramoz Goranci, Yang P. Liu, Richard Peng, Xiaorui Sun, Mingquan Ye
    FOCS 2021
    Proceedings      arXiv
  37. Minimum Cost Flows, MDPs, and ℓ1-Regression in Nearly Linear Time for Dense Instances
    Jan van den Brand, Yin Tat Lee, Yang P. Liu, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, Di Wang
    STOC 2021
    Proceedings      arXiv      Video
  38. Discrepancy Minimization via a Self-Balancing Walk
    Ryan Alweiss, Yang P. Liu, Mehtaab Sawhney
    STOC 2021, Best Student Paper, SIAM Journal of Computing Special Issue
    Journal      Proceedings      arXiv      Slides      Video
  39. Vertex Sparsification for Edge Connectivity
    Parinya Chalermsook, Syamantak Das, Yunbum Kook, Bundit Laekhanukit,
    Yang P. Liu, Richard Peng, Mark Sellke, Daniel Vaz
    SODA 2021
    Proceedings      arXiv      Video
    40. 2020
  40. Faster Divergence Maximization for Faster Maximum Flow
    Yang P. Liu, Aaron Sidford
    FOCS 2020, SIAM Journal of Computing Special Issue
    Journal      Proceedings      arXiv      Slides      Video
  41. Faster Energy Maximization for Faster Maximum Flow
    Yang P. Liu, Aaron Sidford
    STOC 2020
    Proceedings      arXiv      Slides      Video
  42. Constant Girth Approximation for Directed Graphs in Subquadratic Time
    Shiri Chechik, Yang P. Liu, Omer Rotem, Aaron Sidford
    STOC 2020
    Proceedings      arXiv      Slides      Video
  43. Near-optimal Approximate Discrete and Continuous Submodular Function Minimization
    Brian Axelrod, Yang P. Liu, Aaron Sidford
    SODA 2020
    Proceedings      arXiv
  44. On the upper tail problem for random hypergraphs
    Yang P. Liu, Yufei Zhao
    Random Structures & Algorithms
    Journal      arXiv
    45. 2019
  45. Parallel Reachability in Almost Linear Work and Square Root Depth
    Arun Jambulapati, Yang P. Liu, Aaron Sidford
    FOCS 2019
    Proceedings      arXiv      Slides      Video
  46. Short Cycles via Low-Diameter Decompositions
    Yang P. Liu, Sushant Sachdeva, Zejun Yu
    SODA 2019
    Proceedings      arXiv      Slides
  47. Reproducibility and Pseudo-Determinism in Log-Space
    Ofer Grossman, Yang P. Liu
    SODA 2019
    Proceedings      arXiv
    48. Before 2019
  48. An Exponential Separation Between MA and AM Proofs of Proximity
    Tom Gur, Yang P. Liu, Ron D. Rothblum
    ICALP 2018, Computational Complexity
    Journal      Proceedings      ECCC      Slides
  49. The "Riemann Hypothesis" is True for Period Polynomials of Almost All Newforms
    Yang P. Liu, Peter S. Park, Zhuo Qun Song
    Res Math Sci (2016) 3: 31.
    Journal      arXiv
  50. Bounded Gaps Between Products of Distinct Primes
    Yang P. Liu, Peter S. Park, Zhuo Qun Song
    Res. number theory (2017) 3: 26.
    Journal      arXiv