Pith. sign in

REVIEW 4 minor 1 cited by

You can read any coordinate of an approximate top eigenvector of a bounded-entry matrix with only polylog-size local queries.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

A local computation algorithm approximates any coordinate of a top eigenvector of a bounded-entry symmetric matrix with Õ(1/ε²) queries per coordinate (after Õ(1/ε⁴) preprocessing) when negative eigenvalues are not much larger than the top one, with a matching Ω(n/ε²) total-query lower bound and pol

T0 review reviewed 2026-07-10 challenge →

load-bearing objection Solid local top-eigenvector primitive via an explicit lift of SW25 sketches, matching lower bound, and the first poly-time local Cheeger/Trevisan oracles for dense graphs.

arxiv 2607.08556 v1 pith:VOVLCPNM submitted 2026-07-09 cs.DS

Locally Approximating the Top Eigenvector of Bounded Entry Matrices

Nicolas Menand , Erik Waingarten This is my paper
classification cs.DS MSC 68Q2568W2015A1805C50
keywords local computation algorithmstop eigenvectorbounded-entry matricessubspace embeddingCheeger inequalitymax-cutdense graph modelRayleigh quotient
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

A top eigenvector of a huge matrix is a global object: it is defined by an optimization over every entry and itself has n coordinates. This paper shows that when every entry of a symmetric matrix is at most 1 in absolute value, you do not need to look at the whole matrix. After a one-time preprocessing that inspects only a constant-size principal submatrix (roughly 1 over epsilon to the fourth entries), any single coordinate of a nearly-optimal vector can be produced with roughly 1 over epsilon squared further entry probes. The resulting vector certifies an additive epsilon-n approximation to the largest eigenvalue. The same local access immediately yields polynomial-time local algorithms for sparse cuts and max-cuts in dense graphs that achieve the classic square-root approximation guarantees of spectral graph theory, replacing the exponential-in-1/epsilon running times of earlier combinatorial methods. A matching lower bound shows that the per-coordinate query cost cannot be improved.

Core claim

There is a randomized local computation algorithm that, given query access to an n-by-n symmetric matrix with entries in [-1,1], after Õ(1/ε⁴) non-adaptive preprocessing queries answers any requested coordinate of a vector x with Õ(1/ε²) further queries so that, with constant probability, the Rayleigh quotient of x is within additive εn of the largest eigenvalue whenever the spectral norm is comparable to that eigenvalue. When large negative eigenvalues dominate, the same method still works but the exponents rise to roughly 6.6 and 3.3. An Ω(n/ε²) total-query lower bound shows the per-coordinate cost is optimal.

What carries the argument

The lift: once a top eigenvector y of a carefully sampled principal submatrix TATᵀ has been computed, the algorithm returns the vector x = A Tᵀ y / λ̂. Individual coordinates of x require only a single row of A restricted to the sampled columns, and the paper proves that this lift preserves the Rayleigh quotient up to the desired additive error.

Load-bearing premise

The clean Õ(1/ε⁴) preprocessing and Õ(1/ε²) per-coordinate bounds require that the matrix’s largest-magnitude negative eigenvalue is not much larger than its largest positive eigenvalue; otherwise the lift mixes the two eigenspaces and the analysis forces a worse truncation threshold.

What would settle it

Construct an explicit family of bounded-entry matrices whose negative eigenvalues are Θ(n) while the positive ones are only Θ(εn), run the lift algorithm with the claimed Õ(1/ε²) sampling rate, and check whether the output Rayleigh quotient is still within εn of the true maximum; a systematic failure would falsify the good-complexity regime.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

0 major / 4 minor

Summary. The paper gives a local computation algorithm that, given query access to a symmetric n imes n matrix A with entries in [-1,1], after Õ(1/ε^{4}) non-adaptive preprocessing queries returns any coordinate of a vector x with Õ(1/ε^{2}) non-adaptive queries such that, with constant probability, the Rayleigh quotient of x is within additive εn of λ_max(A) whenever ∥A∥_{2} = O(λ_max(A)). When |λ_min| greatly exceeds λ_max the exponents degrade to at most 6.6̅ and 3.3̅. A matching Ω(n/ε^{2}) total-query lower bound is proved even under the same spectral-norm promise. The algorithm is applied to obtain poly(1/ε)-time local algorithms for sparsest cut and max-cut in the dense-graph model that achieve the classical square-root-opt spectral guarantees of Cheeger and Trevisan.

Significance. The work cleanly lifts the eigenvalue-sketching primitive of Swartworth–Woodruff into a local-computation primitive for eigenvectors, with a matching lower bound that shows the per-coordinate cost is optimal. The resulting local spectral algorithms for dense-graph partitioning replace the exponential-in-poly(1/ε) preprocessing of Goldreich–Goldwasser–Ron by polynomial time while retaining the classical square-root approximation factors. The analysis isolates the precise obstruction (negative-eigenvalue interference) and quantifies the resulting geometric-mean degradation, which is a useful contribution in its own right. The technical development is fully self-contained once the imported subspace-embedding and eigenvalue-estimation black boxes are granted.

minor comments (4)
  1. The informal statement of Theorem 1 writes ∥A∥_{2} = O(λ_max(A)) while the formal Theorem 6 and the abstract use |λ_min| = O(λ_max). A single consistent hypothesis would avoid confusion.
  2. In Definition 4.1 the third bullet refers to a “fixed constant c_{0}” for the low-eigenvalue residual; it would help the reader to record that c_{0} is absolute (independent of n and ε).
  3. Appendix B gives a clean rank-2 example of negative-eigenvalue interference; a one-sentence pointer to it already in the introduction (near the discussion of the degraded exponents) would make the limitation more visible.
  4. A few typographical slips remain (e.g., “adjancency”, “Reyni”, “bλmax” versus “λ̂max”). A light copy-edit pass would clean them.

Circularity Check

0 steps flagged

No significant circularity; the LCA, lift analysis, and lower bound are self-contained algorithmic/information-theoretic arguments that treat SW25 subspace embeddings as an external black-box primitive.

full rationale

The central claim (Theorem 6 / Theorem 1) constructs an explicit lift x = A T^⊺ y / λ̂_max of the top eigenvector y of the sketched matrix TAT^⊺ and proves, via mass-control Lemmas 4.13–4.14 and spectral-norm bounds on the distortion matrix M (Lemmas 4.11, 4.16–4.18), that the Rayleigh quotients differ by at most εn whenever the event E of Definition 4.1 holds. Event E is established from the external subspace-embedding and eigenvalue-approximation guarantees of Swartworth–Woodruff (Theorems 5 and 8, cited as [SW25]), which are used strictly as black boxes with stated parameter settings (q = n/L² · polylog, L set by Eq. (4)). The lower bound (Theorem 2) is an independent reduction to the classic coin problem via Yao and an elementary embedding of a single random coordinate; it does not rely on the upper-bound analysis. Applications to sparsest-cut and max-cut simply invoke the same LCA inside the classical sweep-cut arguments of Cheeger and Trevisan. No parameter is fitted to data, no target quantity is redefined in terms of itself, and the sole external citation is to non-overlapping authors. Appendix B explicitly isolates the regime (large negative eigenvalues) where the mass-control fails, confirming the argument is not circularly forced. The derivation is therefore free of the enumerated circularity patterns.

Axiom & Free-Parameter Ledger

3 free parameters · 4 axioms · 0 invented entities

The paper is pure algorithmic theory. It inherits standard matrix-concentration and subspace-embedding facts, works in the established bounded-entry and local-computation models, and introduces no free parameters fitted to data and no new physical or mathematical entities beyond ordinary algorithmic objects (row-sampling matrices, the lift vector).

free parameters (3)
  • accuracy parameter ε
    User-supplied accuracy; not fitted. All complexities are expressed in terms of ε.
  • truncation level L (Eq. 4)
    Algorithmically chosen as a function of ε, λ_max, λ_min and polylog factors so that the error lemmas stay within εn; not data-fitted.
  • absolute constant c for the assumption λ_max ≥ c·εn
    A fixed numerical threshold (Remark 7) that can be absorbed into the choice of ε; not fitted to any dataset.
axioms (4)
  • standard math Matrix Chernoff / subspace-embedding guarantees for row-sampling matrices (Theorem 5, imported from SW25 / Tropp / Kyng)
    Used throughout Section 4 to control distortion of high-magnitude eigenspaces.
  • domain assumption Bounded-entry model ∥A∥_∞ ≤ 1 and the local-computation model of Rubinfeld et al.
    Defines the query model and the scale of additive εn error; standard in the sublinear spectral literature.
  • domain assumption Eigenvalue estimation of SW25 (Theorem 8) supplies additive αL approximations to λ_max and λ_min
    Invoked to set the sampling probability q without asymptotic overhead.
  • standard math Spectral-norm decay of random principal submatrices (Appendix A, after Rudelson–Vershynin / Tropp) with log(nq) rather than log n
    Used to bound the low-eigenvalue portion A_L without an extra log n factor.

reviewed 2026-07-10 · how reviews work

0 comments
Cite this review

Pith. "Pith review of Locally Approximating the Top Eigenvector of Bounded Entry Matrices." pith.science (2026). https://pith.science/paper/VOVLCPNM

@misc{pith2026260708556,
  author       = {Pith},
  title        = {Pith review of: Locally Approximating the Top Eigenvector of Bounded Entry Matrices},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/VOVLCPNM}},
  note         = {Machine review of arXiv:2607.08556}
}
Share X Bluesky LinkedIn Reddit HN
read the original abstract

We provide a local computation algorithm to approximate the top eigenvector $x \in \mathbb{R}^n$ of a symmetric matrix $A \in \mathbb{R}^{n \times n}$ with entries between $-1$ and $1$, building on the work of Swartworth and Woodruff [SODA 25] who show how to approximate the eigenvalues up to additive-$\varepsilon n$ error using $\tilde{O}(1/\varepsilon^4)$ queries. Our local computation algorithm has a preprocessing complexity of $\tilde{O}(1/\varepsilon^4)$ and per-coordinate query complexity of $\tilde{O}(1/\varepsilon^2)$ for an additive-$\varepsilon n$ approximation whenever {$|\lambda_{\min}(A)| = O(\lambda_{\max}(A))$. When $\lambda_{\min}(A)$ greatly exceeds $\lambda_{\max}(A)$, our complexity degrades to at most $\tilde{O}(1/\varepsilon^{6.\overline{6}})$ in preprocessing and $\tilde{O}(1/\varepsilon^{3.\overline{3}})$ per query. Furthermore, we show a lower bound of $\Omega(n/\varepsilon^2)$ on the total number of queries needed to output an approximately top eigenvector (implying that the per-coordinate query complexity of $\Omega(1/\varepsilon^2)$ is necessary). As an application, we use our algorithm to provide local computation algorithms for the sparsest-cut and max-cut problems in the dense graph model of Goldreich, Goldwasser, Ron [JACM 98]. By accessing the top eigenvectors (of an approximate normalized adjacency), we implement local versions of Cheeger's inequality and Trevisan's algorithm [SICOMP 12] to obtain "square-root-opt" approximations in polynomial time (as opposed to exponential-in-$\text{poly}(1/\varepsilon)$ time which is incurred in Goldreich, Goldwasser, Ron.

Figures

Figures reproduced from arXiv: 2607.08556 by Erik Waingarten, Nicolas Menand.

Figure 1
Figure 1. Figure 1: Preprocessing Algorithm Notice that the query complexity of the preprocessing phase is at most t 2 which is at most O((nq) 2 ) with high constant probability. Furthermore, the running time of the preprocessing phase consists of the time needed to compute a top eigenvector y which can be done in poly(t) time up to high precision in the Word-RAM model.8 Having stored the vector y ∈ Rt , the (full) output vec… view at source ↗
Figure 2
Figure 2. Figure 2: Query Algorithm Furthermore, even though the parameter settings below depend on λmax(A) and λmin(A), it suffices to know an additive εn approximation to these, which one can obtain without any asymptotic overhead using the eigenvalue estimation algorithm of [SW25]. Theorem 6. For any n × n symmetric matrix A with ∥A∥∞ ≤ 1 and any ε > 0, let x ∈ Rn be the output of the algorithm on A, initialized with q = m… view at source ↗
Figure 3
Figure 3. Figure 3: Reduction from A satisfying (11) to the Coin Problem. We first upper bound the probability that the reduction in [PITH_FULL_IMAGE:figures/full_fig_p026_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Local Computation Algorithm for Sparsest Cut [PITH_FULL_IMAGE:figures/full_fig_p031_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Local Computation Algorithm for Max Cut (either that “i ∈ L” or “i ∈ R” in some execution of Line 3d, or that “i ∈ L” or “i ∈ R” in Line 4) 21. Hence, we may define L = {i ∈ [n] [PITH_FULL_IMAGE:figures/full_fig_p039_5.png] view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Sublinear Time Eigenvector Approximation via Column Sampling

    cs.DS 2026-08 conditional novelty 8.0

    A small random column sample of a symmetric matrix yields all outlying approximate eigenvectors with small residual error and entrywise query time poly(log n, 1/epsilon).

Reference graph

Works this paper leans on

16 extracted references · 16 canonical work pages · cited by 1 Pith paper

  1. [1]

    [AN13] Alexandr Andoni and Huy L. Nguyen. Eigenvalues of a matrix in the streaming model. In Proceedings of the 24th ACM-SIAM Symposium on Discrete Algorithms (SODA ’2013),

    work page 2013

  2. [2]

    Space-efficient local computation algo- rithms

    [ARVX12] Noga Alon, Ronitt Rubinfeld, Shai Vardi, and Ning Xie. Space-efficient local computation algo- rithms. InProceedings of the 33rd ACM-SIAM Symposium on Discrete Algorithms (SODA ’2012), pages 1132–1139,

    work page 2012

  3. [3]

    Efficient density evaluation for smooth kernels

    [BCIS18] Arturs Backurs, Moses Charikar, Piotr Indyk, and Paris Siminelakis. Efficient density evaluation for smooth kernels. InProceedings of the 59th Annual IEEE Symposium on Foundations of Computer Science (FOCS ’2018), pages 615–626,

    work page 2018

  4. [4]

    Testing positive semi-definiteness via random submatrices

    [BCJ20] Ainesh Bakshi, Nadiia Chepurko, and Rajesh Jayaram. Testing positive semi-definiteness via random submatrices. InProceedings of the 61st Annual IEEE Symposium on Foundations of Computer Science (FOCS ’2020),

    work page 2020

  5. [5]

    Woodruff, and Hongyang Zhang

    [BLWZ19] Maria-Florina Balcan, Yi Li, David P. Woodruff, and Hongyang Zhang. Testing matrix rank, opti- mally. InProceedings of the 30th ACM-SIAM Symposium on Discrete Algorithms (SODA ’2019),

    work page 2019

  6. [6]

    Local computation algorithms for maximum matching: New lower bounds

    [BRR23] Soheil Behnezhad, Mohammad Roghani, and Aviad Rubinstein. Local computation algorithms for maximum matching: New lower bounds. InProceedings of the 64th Annual IEEE Symposium on Foundations of Computer Science (FOCS ’2023),

    work page 2023

  7. [7]

    Sublinear time low-rank approximation of distance matrices

    [BW18] Ainesh Bakshi and David Woodruff. Sublinear time low-rank approximation of distance matrices. InProceedings of Advances in Neural Information Processing Systems 31 (NeurIPS ’2018),

    work page 2018

  8. [8]

    Kernel density estima- tion through density constrained near neighbor search

    [CKNS20] Moses Charikar, Michael Kapralov, Navid Nouri, and Paris Siminelakis. Kernel density estima- tion through density constrained near neighbor search. InProceedings of the 61st Annual IEEE Symposium on Foundations of Computer Science (FOCS ’2020), pages 172–183,

    work page 2020

  9. [9]

    A quasi-monte carlo data structure for smooth kernel evaluations

    [CKW24] Moses Charikar, Michael Kapralov, and Erik Waingarten. A quasi-monte carlo data structure for smooth kernel evaluations. InProceedings of the 35th ACM-SIAM Symposium on Discrete Algorithms (SODA ’2024),

    work page 2024

  10. [10]

    Hashing-based-estimators for kernel density in high dimen- sions

    [CS17] Moses Charikar and Paris Siminelakis. Hashing-based-estimators for kernel density in high dimen- sions. InProceedings of the 58th Annual IEEE Symposium on Foundations of Computer Science (FOCS ’2017), pages 1032–1043,

    work page 2017

  11. [11]

    Local computation of maximal independent set

    [Gha22] Mohsen Ghaffari. Local computation of maximal independent set. InProceedings of the 63rd Annual IEEE Symposium on Foundations of Computer Science (FOCS ’2022),

    work page 2022

  12. [12]

    III: Linear Algebra

    Vol. III: Linear Algebra. [KMS26] Michael Kapralov, Cameron Musco, and Kshiteej Sheth. Sublinear time low-rank approximation of hankel matrices. InProceedings of the 37th ACM-SIAM Symposium on Discrete Algorithms (SODA ’2026),

    work page 2026

  13. [13]

    Recursive sampling for the nystr¨ om method

    [MM17] Cameron Musco and Christopher Musco. Recursive sampling for the nystr¨ om method. InPro- ceedings of Advances in Neural Information Processing Systems (NeurIPS ’2017),

    work page 2017

  14. [14]

    Fast local computation algorithms

    [RTVX11] Ronitt Rubinfeld, Gil Tamir, Shai Vardi, and Ning Xie. Fast local computation algorithms. InProceedings of the 2nd Symposium on Innovations in Computer Science (ICS ’2011), pages 223–238,

    work page 2011

  15. [15]

    Woodruff

    [SW23] William Swartworth and David P. Woodruff. Optimal eigenvalue approximation via sketching. In Proceedings of the 55th ACM Symposium on the Theory of Computing (STOC ’2023),

    work page 2023

  16. [16]

    Woodruff

    [SW25] William Swartworth and David P. Woodruff. Tight sampling bounds for eigenvalue approximation. InProceedings of the 36th ACM-SIAM Symposium on Discrete Algorithms (SODA ’2025),

    work page 2025

This paper was first reviewed by grok-4.5 on July 10, 2026.