{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreidpbhinylh3gitz5mjtuownfgkjpdwxmrefwhfgafrbyxrriot3au",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3mpfvyyqpvi32"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2606.28188v1",
  "publishedAt": "2026-06-29T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Pan Peng",
    "Yuyang Wang",
    "Joy Qiping Yang",
    "Yichun Yang"
  ],
  "textContent": "**Authors:** Pan Peng, Yuyang Wang, Joy Qiping Yang, Yichun Yang\n\nWe 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 $\\varepsilon$-approximate spectral density estimation in the Wasserstein-1 distance, using $2^{O(1/\\varepsilon)}$ random walks initiated from uniformly random nodes in the graph. Later, Jin et al. [COLT 2023] established a nearly matching exponential lower bound for \\emph{weighted} graphs, assuming the algorithm has access to samples from random walks started at random nodes. It was left open whether this lower bound could be extended to \\emph{unweighted} graphs. In this paper, we answer this question in the affirmative by proving an exponential lower bound for unweighted graphs. Specifically, we show that no algorithm can compute an $\\varepsilon$-approximation to the spectrum of a normalized graph adjacency matrix with constant success probability, even when given the full transcripts of $2^{Ω(1/\\varepsilon^{1/6})}$ random walks, each of length $2^{Ω(1/\\varepsilon^{1/6})}$, started from uniformly random nodes.",
  "title": "An Exponential Lower Bound for Spectral Density Estimation on Unweighted Graphs"
}