Constructing linear-sized spectral sparsification in almost-linear time

DOI10.1109/FOCS.2015.24MaRDI QIDQ6946889zbMATH OpenFDO

Authors Yin Tat Lee, He Sun

Publication date 5 August 2025

Full work available at URL https://www.research.ed.ac.uk/en/publications/acf19e1c-684c-4820-960b-523a778e9b81

Mathematics Subject Classification ID

Theory of computing (68Qxx) Discrete mathematics in relation to computer science (68Rxx) Algorithms in computer science (68Wxx)

Cited in

(5)

• Spectral sparsification via bounded-independence sampling
• Better sparsifiers for directed Eulerian graphs
• Eldan's stochastic localization and the KLS conjecture: isoperimetry, concentration and mixing
• Small-space spectral sparsification via bounded-independence sampling
• Sparsification of directed graphs via cut balance

This page was built for publication: Constructing linear-sized spectral sparsification in almost-linear time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6946889)