# Deterministic Spectral Sparsification in Almost-Linear Time for Dense Graphs

Preprint · Jason Li, Trevor Vaughn

- Archive id: arxiv:2608.13910
- Published: 2026-08-14
- arXiv: https://arxiv.org/abs/2608.13910
- Source URL: https://arxiv.org/abs/2608.13910
- PDF: https://arxiv.org/pdf/2608.13910
- Provenance: arxiv

## Abstract

A spectral sparsifier of a weighted graph is a reweighted subgraph whose Laplacian quadratic form approximates that of the original graph. Let $G$ be a positively weighted $n$-vertex, $m$-edge multigraph, let $0\<\\varepsilon\\le1/2$. Assuming $m,\\varepsilon^{-1}\\le n^{O(1)}$ and the ratio of maximum to minimum weight is polynomially bounded, we deterministically construct a $(1\\pm\\varepsilon)$-spectral sparsifier with \\\[ O\\!\\left(n\\varepsilon^{-2}\\log^{24+o(1)}n\\right) \\\] edges in \\\[ m^{1+o(1)}+O\\!\\left(n^2\\varepsilon^{-9/2}\\log^{113/2+o(1)}n\\right) \\\] time. The construction has two main ingredients. First, we sparsify an approximately regular expander by partitioning its edges into few matchings and viewing their normalized Laplacians as an isotropic family of positive semidefinite matrices. Rather than sample from this family and apply matrix Chernoff, we select matchings deterministically using a pessimistic estimator. We evaluate the resulting conditional-expectation scores in two ways to produce two algorithms: using dense matrix multiplication and sparsely using polynomial approximations to the inverse square root and matrix exponential. Deterministic expander decomposition, along with replacing vertices by fixed expander graphs to achieve approximate regularity, extends these algorithms to general graphs. Second, a recursive blocking scheme applies the dense algorithm to smaller subgraphs and the sparse algorithm to their union, balancing their costs. Reusing the resulting algorithm as the dense algorithm gives $α\_{r+1}=3-1/(α\_r-1)$, starting from $α\_0=ω$. After $O(\\log n)$ levels, the exponent is $2+O(1/\\log n)$, yielding $m^{1+o(1)}+\\widetilde O\_{\\varepsilon}(n^2)$ time.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.