# Probabilistic Spectral Sparsification In Sublinear Time

arXiv: https://arxiv.org/abs/1401.0085 · HTML: https://mlsanity.com/paper/1401.0085/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 Dec 2013.

## Built on by (most cited first, 2 of 2)

- [Sublinear Algorithms for Hierarchical Clustering](https://mlsanity.com/paper/2206.07633/) (2022)
- [Faster Spectral Density Estimation and Sparsification in the Nuclear Norm](https://mlsanity.com/paper/2406.07521/) (2024)

## Abstract (arXiv)

In this paper, we introduce a variant of spectral sparsification, called probabilistic (varepsilon,δ)-spectral sparsification. Roughly speaking, it preserves the cut value of any cut (S,Sc) with an 1±varepsilon multiplicative error and a δleft|Sright| additive error. We show how to produce a probabilistic (varepsilon,δ)-spectral sparsifier with O(nlog n/varepsilon2) edges in time tildeO(n/varepsilon2δ) time for unweighted undirected graph. This gives fastest known sub-linear time algorithms for different cut problems on unweighted undirected graph such as - An tildeO(n/OPT+n3/2+t) time O(√log n/t)-approximation algorithm for the sparsest cut problem and the balanced separator problem. - A n1+o(1)/varepsilon4 time approximation minimum s-t cut algorithm with an varepsilon n additive error.