Twice-ramanujan sparsifiers

DOI10.1145/1536414.1536451zbMath1304.05130OpenAlexW2419092805MaRDI QIDQ5172719

Nikhil Srivastava, Joshua Batson, Daniel A. Spielman

Publication date: 4 February 2015

Published in: Proceedings of the forty-first annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1536414.1536451

zbMATH Keywords

spectral graph theoryexpander graphs

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 (30)

Controlling the least eigenvalue of a random Gram matrix ⋮ Deterministic algorithms for matrix completion ⋮ Constructing all self-adjoint matrices with prescribed spectrum and diagonal ⋮ On the convergence of the extremal eigenvalues of empirical covariance matrices with dependence ⋮ Constructive subsampling of finite frames with applications in optimal function recovery ⋮ Simpler is better: a comparative study of randomized pivoting algorithms for CUR and interpolative decompositions ⋮ Sparse reliable graph backbones ⋮ On Sufficient Conditions in the Marchenko--Pastur Theorem ⋮ Tensor sparsification via a bound on the spectral norm of random tensors: Algorithm 1. ⋮ Small Ball Probability for the Condition Number of Random Matrices ⋮ Optimal CUR Matrix Decompositions ⋮ BRASCAMP–LIEB INEQUALITY AND QUANTITATIVE VERSIONS OF HELLY'S THEOREM ⋮ On the sum of a Sobolev space and a weighted \(L_p\)-space ⋮ Feature Selection for Ridge Regression with Provable Guarantees ⋮ A few remarks on sampling of signals with small spectrum ⋮ Extracting a basis with fixed block inside a matrix ⋮ Random approximation and the vertex index of convex bodies ⋮ Quantitative Helly-type theorem for the diameter of convex sets ⋮ An elementary proof of the restricted invertibility theorem ⋮ Randomized least-squares with minimal oversampling and interpolation in general spaces ⋮ Optimal experimental design: formulations and computations ⋮ A distributed algorithm for spectral sparsification of graphs with applications to data clustering ⋮ A General Framework for Graph Sparsification ⋮ Tight embedding of subspaces of 𝐿_{𝑝} in ℓ_{𝑝}ⁿ for even 𝑝 ⋮ Unnamed Item ⋮ Cutting Corners Cheaply, or How to Remove Steiner Points ⋮ Randomized Approximation of the Gram Matrix: Exact Computation and Probabilistic Bounds ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Sobolev extension by linear operators

This page was built for publication: Twice-ramanujan sparsifiers