Junzhao Yang

activity

20242026

collaborators

8 papers

cs.DS2026

Fully Dynamic Random-Walk Quantities on Undirected Expanders and $κ$ -Uniform Directed Graphs

Richard Peng, Sushant Sachdeva, Junzhao Yang +1

We study fully dynamic data structures for random-walk quantities on undirected expanders and fast-mixing directed graphs. For an unweighted graph whose normalized Laplacian has sp…

cs.DS2026

Approximating Random Walks in $O (lo g n + lo g^{2} κ)$ Space for $κ$ -Conditioned Graphs

Junzhao Yang

For $κ > 1$ , a directed graph is $κ$ -conditioned if it is $κ$ -mixing and its stationary distribution is approximated by the uniform distribution within a factor of $κ$ . We present 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

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…

cs.DS2024

Entrywise Approximate Laplacian Solving

Jingbang Chen, Mehrdad Ghadiri, Hoai-An Nguyen +2

We study the escape probability problem in random walks over graphs. Given vertices, $s, t,$ and $p$ , the problem asks for the probability that a random walk starting at $s$ will hi…

Fully Dynamic Random-Walk Quantities on Undirected Expanders and κ-Uniform Directed Graphs

Approximating Random Walks in O(logn+log2κ) Space for κ-Conditioned Graphs

Adaptive Matrix Sparsification and Applications to Empirical Risk Minimization

Entrywise Approximate Solutions for SDDM Systems in Almost-Linear Time

Numerical Linear Algebra in Linear Space

Approximate Spanning Tree Counting from Uncorrelated Edge Sets

Entrywise Approximation for Matrix Inversion and Linear Systems

Entrywise Approximate Laplacian Solving

Fully Dynamic Random-Walk Quantities on Undirected Expanders and $κ$ -Uniform Directed Graphs

Approximating Random Walks in $O (lo g n + lo g^{2} κ)$ Space for $κ$ -Conditioned Graphs