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
Local Computation Algorithms for (Minimum) Spanning Trees on Expander Graphs
Pan Peng, Yuyang Wang
We study \emph{local computation algorithms (LCAs)} for constructing spanning trees. In this setting, the goal is to locally determine, for each edge , whether it belong…