Computer Science Research

On Approximate Fully-Dynamic Matching and Online Matrix-Vector Multiplication, FOCS 2024
Yang P. Liu
arXiv

Almost-Linear Time Algorithms for Decremental Graphs: Min-Cost Flow and More via Duality, FOCS 2024
Jan van den Brand, Li Chen, Rasmus Kyng, Yang P. Liu, Simon Meierhans, Maximilian Probst Gutenberg, Sushant Sachdeva
arXiv

Sparsifying generalized linear models, STOC 2024
Arun Jambulapati, James R. Lee, Yang P. Liu, Aaron Sidford
arXiv      Proceedings      Slides      Video

Almost-Linear Time Algorithms for Incremental Graphs: Cycle Detection, SCCs, s-t Shortest Path, and Minimum-Cost Flow, STOC 2024
Li Chen, Rasmus Kyng, Yang P. Liu , Simon Meierhans, Maximilian Probst Gutenberg
arXiv      Proceedings

Incremental Approximate Maximum Flow on Undirected Graphs in Subpolynomial Update Time, SODA 2024
Jan van den Brand, Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, Sushant Sachdeva, Aaron Sidford
arXiv

A Deterministic Almost-Linear Time Algorithm for Minimum-Cost Flow, FOCS 2023
Jan van den Brand, Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, Sushant Sachdeva, Aaron Sidford
arXiv

Sparsifying Sums of Norms, FOCS 2023, Invited to SICOMP Special Issue
Arun Jambulapati, James R. Lee, Yang P. Liu, Aaron Sidford
arXiv

Chaining, Group Leverage Score Overestimates, and Fast Spectral Hypergraph Sparsification, STOC 2023
Arun Jambulapati, Yang P. Liu, Aaron Sidford
Proceedings      arXiv

Dynamic Maxflow via Dynamic Interior Point Methods, STOC 2023
Jan van den Brand, Yang P. Liu, Aaron Sidford
Proceedings      arXiv

Vertex Sparsification for Edge Connectivity in Polynomial Time, ITCS 2023
Yang P. Liu
Proceedings      arXiv

Optimal Sublinear Sampling of Spanning Trees and Determinantal Point Processes via Average-Case Entropic Independence, FOCS 2022, Invited to SICOMP Special Issue
Nima Anari, Yang P. Liu, Thuy-Duong Vuong
Proceedings      arXiv

Maximum Flow and Minimum-Cost Flow in Almost Linear Time, FOCS 2022, Best Paper
Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, Sushant Sachdeva
arXiv      Slides      Video

Online Edge Coloring via Tree Recurrences and Correlation Decay, STOC 2022, Invited to SICOMP Special Issue
Janardhan Kulkarni, Yang P. Liu, Ashwin Sah, Mehtaab Sawhney, Jakub Tarnawski
Proceedings      arXiv

Improved Iteration Complexities for Overconstrained p-Norm Regression, STOC 2022
Arun Jambulapati, Yang P. Liu, Aaron Sidford
Proceedings      arXiv

Faster Maxflow via Improved Dynamic Spectral Vertex Sparsifiers, STOC 2022
Jan van den Brand, Yu Gao, Arun Jambulapati, Yin Tat Lee, Yang P. Liu, Richard Peng, Aaron Sidford
Proceedings      arXiv

A Gaussian Fixed Point Walk, ITCS 2022, Best Student Paper
Yang P. Liu, Ashwin Sah, Mehtaab Sawhney
Proceedings      arXiv      Slides      Video

Fully Dynamic Electrical Flows: Sparse Maxflow Faster Than Goldberg-Rao, FOCS 2021, SIAM Journal of Computing Special Issue
Yu Gao, Yang P. Liu, Richard Peng
Journal      Proceedings      arXiv      Slides      Video

Minor Sparsifiers and the Distributed Laplacian Paradigm, FOCS 2021
Sebastian Forster, Gramoz Goranci, Yang P. Liu, Richard Peng, Xiaorui Sun, Mingquan Ye
Proceedings      arXiv

Minimum Cost Flows, MDPs, and ℓ1-Regression in Nearly Linear Time for Dense Instances, STOC 2021
Jan van den Brand, Yin Tat Lee, Yang P. Liu, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, Di Wang
Proceedings      arXiv      Video

Discrepancy Minimization via a Self-Balancing Walk, STOC 2021, Best Student Paper, SIAM Journal of Computing Special Issue
Ryan Alweiss, Yang P. Liu, Mehtaab Sawhney
Proceedings      arXiv      Slides      Video

Vertex Sparsification for Edge Connectivity, SODA 2021
Parinya Chalermsook, Syamantak Das, Yunbum Kook, Bundit Laekhanukit,
Yang P. Liu, Richard Peng, Mark Sellke, Daniel Vaz
Proceedings      arXiv      Video

Faster Divergence Maximization for Faster Maximum Flow, FOCS 2020, SIAM Journal of Computing Special Issue
Yang P. Liu, Aaron Sidford
Journal      Proceedings      arXiv      Slides      Video

Faster Energy Maximization for Faster Maximum Flow, STOC 2020
Yang P. Liu, Aaron Sidford
Proceedings      arXiv      Slides      Video

Constant Girth Approximation for Directed Graphs in Subquadratic Time, STOC 2020
Shiri Chechik, Yang P. Liu, Omer Rotem, Aaron Sidford
Proceedings      arXiv      Slides      Video

Near-optimal Approximate Discrete and Continuous Submodular Function Minimization, SODA 2020
Brian Axelrod, Yang P. Liu, Aaron Sidford
Proceedings      arXiv

Parallel Reachability in Almost Linear Work and Square Root Depth, FOCS 2019
Arun Jambulapati, Yang P. Liu, Aaron Sidford
Proceedings      arXiv      Slides      Video

Short Cycles via Low-Diameter Decompositions, SODA 2019
Yang P. Liu, Sushant Sachdeva, Zejun Yu
Proceedings      arXiv      Slides

Reproducibility and Pseudo-Determinism in Log-Space, SODA 2019
Ofer Grossman, Yang P. Liu
Proceedings      arXiv

An Exponential Separation Between MA and AM Proofs of Proximity, ICALP 2018
Tom Gur, Yang P. Liu, Ron D. Rothblum
Proceedings      ECCC      Slides


Mathematics Research

On the upper tail problem for random hypergraphs, Random Structures & Algorithms
Yang P. Liu, Yufei Zhao
Journal      arXiv

Arithmetic progressions in sumsets of sparse sets, Integers
Noga Alon, Ryan Alweiss, Yang P. Liu, Anders Martinsson, Shyam Narayanan
Journal      arXiv

The "Riemann Hypothesis" is True for Period Polynomials of Almost All Newforms,
Res Math Sci (2016) 3: 31.
Yang P. Liu, Peter S. Park, Zhuo Qun Song
Journal      arXiv

Bounded Gaps Between Products of Distinct Primes, Res. number theory (2017) 3: 26.
Yang P. Liu, Peter S. Park, Zhuo Qun Song
Journal      arXiv


Manuscripts

Exponential Convergence of Sinkhorn Under Regularization Scheduling, ACDA 2024
Jingbang Chen, Yang P. Liu, Richard Peng, Arvind Ramaswami
arXiv