Sparsifying generalized linear models, STOC 2024
Arun Jambulapati, James R. Lee, Yang P. Liu, Aaron Sidford
arXiv 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
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
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
Bounded Gaps Between Products of Distinct Primes, Res. number theory (2017) 3: 26.
Yang P. Liu, Peter S. Park, Zhuo Qun Song
Journal arXiv
Exponential Convergence of Sinkhorn Under Regularization Scheduling , manuscript
Jingbang Chen, Yang P. Liu, Richard Peng, Arvind Ramaswami
arXiv