{"ID":6267241,"CreatedAt":"2026-07-10T01:11:38.759438437Z","UpdatedAt":"2026-07-13T01:02:08.706470581Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.08556","arxiv_id":"2607.08556","title":"Locally Approximating the Top Eigenvector of Bounded Entry Matrices","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 {$|λ_{\\min}(A)| = O(λ_{\\max}(A))$. When $λ_{\\min}(A)$ greatly exceeds $λ_{\\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 $Ω(n/\\varepsilon^2)$ on the total number of queries needed to output an approximately top eigenvector (implying that the per-coordinate query complexity of $Ω(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.","short_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$ e...","url_abs":"https://arxiv.org/abs/2607.08556","url_pdf":"https://arxiv.org/pdf/2607.08556v1","authors":"[\"Nicolas Menand\",\"Erik Waingarten\"]","published":"2026-07-09T14:47:06Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}