4 papers · 1 filter
An algorithm for counting spanning trees by -regularized resistance
Rong-Hua Li, Yichun Yang
We study the basic problem of approximating the number of spanning trees of a graph. For a graph with vertices, edges, We propose an algorithm that approximates the number…
Fast counting and sampling for ferromagnetic two-spin systems
Weiming Feng, Heng Guo, Yichun Yang
We introduce two new models equivalent to ferromagnetic two-spin systems: a weighted subgraph model and a random cluster type model. Using these new connections, we obtain an effic…
An Exponential Lower Bound for Spectral Density Estimation on Unweighted Graphs
Pan Peng, Yuyang Wang, Joy Qiping Yang +1
We study lower bounds for estimating the spectral density of the normalized adjacency matrix of a graph. Previously, Cohen-Steiner et al. [KDD 2018] proposed an algorithm for $\var…
Improved Algorithms for Effective Resistance Computation on Graphs
Yichun Yang, Rong-Hua Li, Meihao Liao +1
Effective Resistance (ER) is a fundamental tool in various graph learning tasks. In this paper, we address the problem of efficiently approximating ER on a graph $\mathcal{G}=(\mat…