4 papers
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…
Quantum Algorithms for Triangle Cut Sparsification
Shan Jiang, Pan Peng
Triangles capture higher-order structures in graphs and are fundamental to applications such as clustering and network analysis. To enable efficient use of such structures at scale…
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…
Quantum Property Testing for Bounded-Degree Directed Graphs
Pan Peng, Jingyu Wu
We study quantum property testing for directed graphs with maximum in-degree and out-degree bounded by some universal constant . For a proximity parameter , we show…