Small-space spectral sparsification via bounded-independence sampling
From MaRDI portal
Cites work
- A fast and simple randomized parallel algorithm for the maximal independent set problem
- A matrix hyperbolic cosine algorithm and applications
- A Nearly-m log n Time Solver for SDD Linear Systems
- A new approach to computing maximum flows using electrical flows
- A new series of dense graphs of high girth
- A Simple Parallel Algorithm for the Maximal Independent Set Problem
- A simple, combinatorial algorithm for solving SDD systems in nearly-linear time
- Almost Optimal Explicit Johnson-Lindenstrauss Families
- Almost-linear-time algorithms for Markov chains and new spectral primitives for directed graphs
- An almost-linear time algorithm for uniform random spanning tree generation
- An almost-linear-time algorithm for approximate max flow in undirected graphs, and its multicommodity generalizations
- An efficient parallel solver for SDD linear systems
- An SDP-based algorithm for linear-sized spectral sparsification
- Approaching optimality for solving SDD linear systems
- Approximate Gaussian elimination for Laplacians -- fast, sparse, and simple
- Approximating the exponential, the lanczos method and an Õ(m)-time spectral algorithm for balanced separator
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- Cognitive Networked Sensing and Big Data
- Computational Complexity
- Computational Complexity
- Constructing linear-sized spectral sparsification in almost-linear time
- Derandomization beyond connectivity: undirected Laplacian systems in nearly logarithmic space
- Dynamic cage survey
- Efficient accelerated coordinate descent methods and faster algorithms for solving linear systems
- Electrical flows, Laplacian systems, and faster approximation of maximum flow in undirected graphs
- Fast generation of random spanning trees and the effective resistance metric
- Faster algorithms for computing the stationary distribution, simulating random walks, and more
- Faster Generation of Random Spanning Trees
- Graph sparsification by effective resistances
- Graph sparsification, spectral sketches, and faster resistance computation, via short cycle decompositions
- scientific article; zbMATH DE number 1256718 (Why is no real title available?)
- scientific article; zbMATH DE number 3189017 (Why is no real title available?)
- scientific article; zbMATH DE number 3061533 (Why is no real title available?)
- scientific article; zbMATH DE number 7650109 (Why is no real title available?)
- Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
- Negative-weight shortest paths and unit capacity minimum cost flow in \(\tilde{O}(m^{10/7}\log W)\) time (extended abstract)
- Note on the girth of Ramanujan graphs
- On a set of almost deterministic k-independent random variables
- Probabilistic logarithmic-space algorithms for Laplacian solvers
- Ramanujan graphs
- Sampling from large matrices
- Solving directed Laplacian systems in nearly-linear time through sparse LU factorizations
- Solving SDD linear systems in nearly \(m \log^{1/2} n\) time
- Sparsified Cholesky and multigrid solvers for connection Laplacians
- Spectral sparsification and regret minimization beyond matrix multiplicative updates
- The masked sample covariance estimator: an analysis using matrix concentration inequalities
- There are planar graphs almost as good as the complete graph
- Twice-Ramanujan sparsifiers
- Undirected connectivity in log-space
This page was built for publication: Small-space spectral sparsification via bounded-independence sampling
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7022390)
