Junzhao Yang

activity

20242026

collaborators

Showing 2025Show all

5 papers · 1 filter

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

Entrywise Approximate Solutions for SDDM Systems in Almost-Linear Time

Angelo Farfan, Mehrdad Ghadiri, Junzhao Yang

We present an algorithm that given any invertible symmetric diagonally dominant M-matrix (SDDM), i.e., a principal submatrix of a graph Laplacian, $L$ and a n…

cs.DS2025

Numerical Linear Algebra in Linear Space

Yiping Liu, Hoai-An Nguyen, Junzhao Yang

We present a randomized linear-space solver for general linear systems $Ax = b$ with $A \in Z^{n \times n}$ and $\mathbf{b} \in \mathb…

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.DS2025

Entrywise Approximation for Matrix Inversion and Linear Systems

Mehrdad Ghadiri, Hoai-An Nguyen, Junzhao Yang

We study the bit complexity of inverting diagonally dominant matrices, which are associated with random walk quantities such as hitting times and escape probabilities. Such quantit…