8 citations · 24 across the 23 of their papers we have counts for
22 papers · 1 filter
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…
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…
Massively Parallel Algorithms for the Stochastic Block Model
Zelin Li, Pan Peng, Xianbin Zhu
Learning the community structure of a large-scale graph is a fundamental problem in machine learning, computer science and statistics. We study the problem of exactly recovering th…
Effective Resistances in Non-Expander Graphs
Dongrun Cai, Xue Chen, Pan Peng
Effective resistances are ubiquitous in graph algorithms and network analysis. In this work, we study sublinear time algorithms to approximate the effective resistance of an adjace…
An Optimal Separation between Two Property Testing Models for Bounded Degree Directed Graphs
Pan Peng, Yuyang Wang
We revisit the relation between two fundamental property testing models for bounded-degree directed graphs: the bidirectional model in which the algorithms are allowed to query bot…
Sublinear-Time Algorithms for Max Cut, Max E2Lin, and Unique Label Cover on Expanders
Pan Peng, Yuichi Yoshida
We show sublinear-time algorithms for Max Cut and Max E2Lin on expanders in the adjacency list model that distinguishes instances with the optimal value more than $1-\varepsil…