Twice-Ramanujan Sparsifiers

DOI10.1137/090772873zbMath1260.05092OpenAlexW2067081844MaRDI QIDQ4910582

Joshua Batson, Nikhil Srivastava, Daniel A. Spielman

Publication date: 19 March 2013

Published in: SIAM Journal on Computing (Search for Journal in Brave)

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

zbMATH Keywords

barrier method spectral graph theory spectral sparsification sparse quadratic forms rank-one updates graph sparsification paving 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) Signed and weighted graphs (05C22)

Related Items (48)

The Marcinkiewicz-type discretization theorems ⋮ Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving ⋮ Lunin's method for selecting large submatrices with small norm ⋮ Interlacing families. III: Sharper restricted invertibility estimates ⋮ Graphs, Vectors, and Matrices ⋮ Enhancing Pure-Pixel Identification Performance via Preconditioning ⋮ Relating the Time Complexity of Optimization Problems in Light of the Exponential-Time Hypothesis ⋮ Minimum Cuts and Sparsification in Hypergraphs ⋮ Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time ⋮ Interlacing Families IV: Bipartite Ramanujan Graphs of All Sizes ⋮ Shape Simplification Through Graph Sparsification ⋮ Proportional Volume Sampling and Approximation Algorithms for A-Optimal Design ⋮ Covariance estimation for distributions with ${2+\varepsilon}$ moments ⋮ A Local Search Framework for Experimental Design ⋮ A Spectral Approach to Network Design ⋮ On the convergence of the extremal eigenvalues of empirical covariance matrices with dependence ⋮ Sparsification of Binary CSPs ⋮ Dimension reduction for finite trees in $\ell_1$ ⋮ Comparison of matrix norm sparsification ⋮ The algebraic structure of the densification and the sparsification tasks for CSPs ⋮ Graph Sparsification, Spectral Sketches, and Faster Resistance Computation via Short Cycle Decompositions ⋮ Remarks on sampling discretization of integral norms of functions ⋮ Unnamed Item ⋮ Universal sampling discretization ⋮ Geometric bounds on the fastest mixing Markov chain ⋮ Restricted Invertibility Revisited ⋮ Faster cut sparsification of weighted graphs ⋮ Four deviations suffice for rank 1 matrices ⋮ Resilience: A Criterion for Learning in the Presence of Arbitrary Outliers ⋮ Steiner Point Removal with Distortion $O(\log {k})$ using the Relaxed-Voronoi Algorithm ⋮ Turning Big Data Into Tiny Data: Constant-Size Coresets for $k$-Means, PCA, and Projective Clustering ⋮ The exponential-time hypothesis and the relative complexity of optimization and logical reasoning problems ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Entropy numbers and Marcinkiewicz-type discretization ⋮ Random projections for Bayesian regression ⋮ Integral norm discretization and related problems ⋮ Sparsification of Binary CSPs ⋮ On‐line balancing of random inputs ⋮ Approximation Algorithms for D-optimal Design ⋮ On Computationally Tractable Selection of Experiments in Measurement-Constrained Regression Models ⋮ Upper and lower bounds for matrix discrepancy ⋮ Randomized Approximation of the Gram Matrix: Exact Computation and Probabilistic Bounds ⋮ The legacy of Jean Bourgain in geometric functional analysis ⋮ Randomized Approximation Schemes for Cuts and Flows in Capacitated Graphs ⋮ Continuous quantitative Helly-type results ⋮ Interlacing families. II: Mixed characteristic polynomials and the Kadison-Singer problem ⋮ Zonoids and sparsification of quantum measurements

This page was built for publication: Twice-Ramanujan Sparsifiers