Yang P. Liu

activity

20242026

most citedOn Approximate Fully-Dynamic Matching and Online Matrix-Vector Multiplication

1 citations · 1 across the 4 of their papers we have counts for

collaborators

Showing cs.DSShow all

6 papers · 1 filter

cs.DS2026

Near-Optimal Oracle Bounds for Isotropic Rounding

Yang P. Liu, Richard Peng, Alicia Stepin +1

We give optimal bounds, up to polylogarithmic factors, for rounding convex bodies to near-isotropic position. A convex body $B (0, r) \subseteq K \subseteq B (0, R)$ in $R^{n}$ can be rou…

cs.DS2025

Adaptive Matrix Sparsification and Applications to Empirical Risk Minimization

Yang P. Liu, Richard Peng, Colin Tang +2

Consider the empirical risk minimization (ERM) problem, which is stated as follows. Let $K_{1}, \dots, K_{m}$ be compact convex sets with $K_{i} \subseteq R^{n_{i}}$ for $i \in [m…

cs.DS2025

Sparsifying Sums of Positive Semidefinite Matrices

Arpon Basu, Pravesh K. Kothari, Yang P. Liu +1

In this paper, we revisit spectral sparsification for sums of arbitrary positive semidefinite (PSD) matrices. Concretely, for any collection of PSD matrices $\mathcal{A} = \{A_1, A…

cs.DS2025

Incremental Shortest Paths in Almost Linear Time via a Modified Interior Point Method

Yang P. Liu

We give an algorithm that takes a directed graph $G$ undergoing $m$ edge insertions with lengths in $[1, W]$ , and maintains $(1 + ε)$ -approximate shortest path distances from a fixed…

cs.DS2025

Approximate Spanning Tree Counting from Uncorrelated Edge Sets

Yang P. Liu, Richard Peng, Junzhao Yang

We show an $O (m^{1.5} ε^{- 1})$ time algorithm that on a graph with $m$ edges and $n$ vertices outputs its spanning tree count up to a multiplicative $(1 + ε)$ factor with…

cs.DS2024★ 1 cited

On Approximate Fully-Dynamic Matching and Online Matrix-Vector Multiplication

Yang P. Liu

We study connections between the problem of fully dynamic $(1 - ε)$ -approximate maximum bipartite matching, and the dual $(1 + ε)$ -approximate vertex cover problem, with the online mat…