Spectral sparsification via random spanners

DOI10.1145/2090236.2090267zbMath1347.68364OpenAlexW2002894241MaRDI QIDQ2826071

Rina Panigrahy, Michael Kapralov

Publication date: 7 October 2016

Published in: Proceedings of the 3rd Innovations in Theoretical Computer Science Conference (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)

Related Items (10)

Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving ⋮ A combinatorial cut-toggling algorithm for solving Laplacian linear systems ⋮ Graph Sparsification, Spectral Sketches, and Faster Resistance Computation via Short Cycle Decompositions ⋮ Decentralized Low-Stretch Trees via Low Diameter Graph Decompositions ⋮ Single Pass Spectral Sparsification in Dynamic Streams ⋮ Density Independent Algorithms for Sparsifying k-Step Random Walks ⋮ Bypassing Erdős’ Girth Conjecture: Hybrid Stretch and Sourcewise Spanners ⋮ Unnamed Item ⋮ A General Framework for Graph Sparsification ⋮ Sparsification of Two-Variable Valued Constraint Satisfaction Problems

Cites Work

• Unnamed Item
• The reproducible properties of correct forecasts
• The dimensions of individual strings and sequences
• Effective Strong Dimension in Algorithmic Information and Computational Complexity
• The Complexity of Forecast Testing
• The Well-Calibrated Bayesian
• Asymptotic calibration
• Dimension in Complexity Classes
• Universal prediction
• THE FRACTIONAL DIMENSION OF A SET DEFINED BY DECIMAL PROPERTIES

This page was built for publication: Spectral sparsification via random spanners