Twice-Ramanujan Sparsifiers

DOI10.1137/130949117zbMath1311.05108OpenAlexW2169871260MaRDI QIDQ5166327

Nikhil Srivastava, Joshua Batson, Daniel A. Spielman

Publication date: 26 June 2014

Published in: SIAM Review (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/130949117

zbMATH Keywords

barrier methodspectral graph theoryspectral sparsificationsparse quadratic formsrank-one updatesgraph sparsificationpaving conjecture

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Positive matrices and their generalizations; cones of matrices (15B48) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (20)

Randomized numerical linear algebra: Foundations and algorithms ⋮ Sampling discretization and related problems ⋮ Exponential frames on unbounded sets ⋮ On sampling discretization in \(L_2\) ⋮ A Quantitative Helly-Type Theorem: Containment in a Homothet ⋮ Finding Sparse Solutions for Packing and Covering Semidefinite Programs ⋮ Semi-Infinite Linear Regression and Its Applications ⋮ Some improved bounds in sampling discretization of integral norms ⋮ A sharp upper bound for sampling numbers in \(L_2\) ⋮ Unnamed Item ⋮ Interactions of computational complexity theory and mathematics ⋮ Reconstruction of Signals: Uniqueness and Stable Sampling ⋮ Sampling discretization of the uniform norm ⋮ Core-Sets: Updated Survey ⋮ On optimal recovery in \(L_2\) ⋮ Oracle-Based Primal-Dual Algorithms for Packing and Covering Semidefinite Programs ⋮ Optimal pointwise sampling for \(L^2\) approximation ⋮ Subset selection for matrices with fixed blocks ⋮ Approximation of the average of some random matrices ⋮ Sparsification of Two-Variable Valued Constraint Satisfaction Problems

This page was built for publication: Twice-Ramanujan Sparsifiers