Yang P. Liu

collaborators

4 papers

cs.DS2026

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

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

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 + I^µ)$ -approximate shortest path distances from a fixe…

cs.DS2025

Approximate Spanning Tree Counting from Uncorrelated Edge Sets

Yang P. Liu, Richard Peng, Junzhao Yang

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