Showing cs.DSShow all
2 papers · 1 filter
cs.DS2026
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…
cs.DS2026
Sublinear Spectral Clustering Oracle with Little Memory
Ranran Shen, Xiaoyi Zhu, Pan Peng +1
We study the problem of designing \emph{sublinear spectral clustering oracles} for well-clusterable graphs. Such an oracle is an algorithm that, given query access to the adjacency…