MathDB

Spectral density estimation under local graph access

Given local random-neighbor access to an unknown unweighted graph GG with nn vertices, let NGN_G denote its normalized adjacency matrix and let μG=1n∑i=1nδλi(NG)\mu_G=\frac{1}{n}\sum_{i=1}^{n}\delta_{\lambda_i(N_G)} be its spectral density. Determine the query complexity, as a function of ε\varepsilon, of producing an estimator μ^\widehat\mu such that, with constant success probability, W1(μ^,μG)≤εW_1(\widehat\mu,\mu_G)\leq\varepsilon. In particular, establish whether every such classical estimator requires 2Ω(1/ε)2^{\Omega(1/\varepsilon)} local queries, matching the known 2O(1/ε)2^{O(1/\varepsilon)} upper bound.

References

Primary source

arXiv

Additional references

graph-algorithmsquantum-computingtheoretical-computer-science
Posted

Progress summary

Refreshed
Claimed solved

A new preprint claims the conjectured exponential number of local questions is necessary, matching the best known method, but its proof has not been independently verified.

The problem asks whether estimating a graph’s eigenvalue distribution from local random-neighbor access necessarily requires exponentially many queries as the accuracy improves.

Known results

  • Cohen-Steiner, Kong, Sohler, and Valiant, 2018: a 2O(1/ε)2^{O(1/\varepsilon)} classical estimator in the random-neighbor model.
  • Jin, Musco, Sidford, and Singh, 2023: a nearly matching 2Ω(1/ε)2^{\Omega(1/\varepsilon)} lower bound for weighted graphs.
  • Peng, 2026: for unweighted graphs and non-adaptive random-walk transcripts, mT>2c/ε1/6mT>2^{c/\varepsilon^{1/6}}; the adaptive local-access case was left open.

August 2026 claimed resolution

The preprint Classical and quantum spectral density estimation under local graph access claims that every randomized classical estimator requires at least 2c/ε2^{c/\varepsilon} queries for sufficiently small ε\varepsilon, with constant success probability. Together with the known upper bound, this would establish 2Θ(1/ε)2^{\Theta(1/\varepsilon)} complexity; the claim is unrefereed and unverified.

Current status (as of August 2026): The classical question is claimed resolved at 2Θ(1/ε)2^{\Theta(1/\varepsilon)}, but the new lower-bound proof remains unverified.

Sources

Solutions 0

No solutions have been posted yet.