Fetching the paper…
Reading the bibliography…
We show variants of spectral sparsification routines can preserve the total spanning tree counts of graphs, which by Kirchhoff's matrix-tree theorem, is equivalent to determinant of a graph Laplacian minor, or equivalently, of any SDDM matrix.
The complexity of partial derivatives
Walter Baur and Volker Strassen · 1983
Earlier work this paper cites.
Random spanning tree
Alain Guenoche · 1983
Earlier work this paper cites.
Self-adjusting binary search trees
Daniel Dominic Sleator and Robert Endre Tarjan · 1985
Earlier work this paper cites.
Generating random spanning trees
Andrei Broder · 1989
Earlier work this paper cites.
Unranking and ranking spanning trees of a graph
Charles J Colbourn, Robert PJ Day, and Louis D Nel · 1989
Earlier work this paper cites.
The random walk construction of uniform spanning trees and uniform labelled trees
David Aldous · 1990
Earlier work this paper cites.
Generating random combinatorial objects
Vidyadhar G. Kulkarni · 1990
Earlier work this paper cites.
Local characteristics, entropy and limit theorems for spanning trees and domino tilings via transfer-impedances
Robert Burton and Robin Pemantle · 1993
Earlier work this paper cites.
The numbers of spanning trees, hamilton cycles and perfect matchings in a random graph
Svante Janson · 1994
Earlier work this paper cites.
Approximating s-t minimum cuts in Õ(n2) time
András A. Benczúr and David R. Karger · 1996
Earlier work this paper cites.
Two algorithms for unranking arborescences
Charles J Colbourn, Wendy J Myrvold, and Eugene Neufeld · 1996
Earlier work this paper cites.
Sparsification—a technique for speeding up dynamic graph algorithms
David Eppstein, Zvi Galil, Giuseppe F. Italiano, and Amnon Nissenzweig · 1997
Earlier work this paper cites.
Maintaining information in fully dynamic trees with top trees
Stephen Alstrup, Jacob Holm, Kristian De Lichtenberg, and Mikkel Thorup · 2005
Earlier work this paper cites.
Expanders via random spanning trees
Navin Goyal, Luis Rademacher, and Santosh Vempala · 2009
Earlier work this paper cites.
Faster generation of random spanning trees
Jonathan Kelner and Aleksander Madry · 2009
Cited alongside, same era.
An o(log n/ log log n)-approximation algorithm for the asymmetric traveling salesman problem
Arash Asadpour, Michel X. Goemans, Aleksander Madry, Shayan Oveis Gharan, and Amin Saberi · 2010
Cited alongside, same era.
A general framework for graph sparsification
Wai Shing Fung, Ramesh Hariharan, Nicholas JA Harvey, and Debmalya Panigrahi · 2011
Cited alongside, same era.
Determinant approximations, 2011
Ilse C. F. Ipsen and Dean J. Lee · 2011
Cited alongside, same era.
Graph sparsification by effective resistances
Daniel A. Spielman and Nikhil Srivastava · 2011
Cited alongside, same era.
Spectral sparsification of graphs
Nearly linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems
Daniel A. Spielman and Shang-Hua Teng · 2014
Later among the works it cites.
A randomized algorithm for approximating the log determinant of a symmetric positive definite matrix
Christos Boutsidis, Petros Drineas, Prabhanjan Kambadur, and Anastasios Zouzias · 2015
Later among the works it cites.
A randomized algorithm for approximating the log determinant of a symmetric positive definite matrix
Christos Boutsidis, Petros Drineas, Prabhanjan Kambadur, and Anastasios Zouzias · 2015
Later among the works it cites.
Efficient sampling for Gaussian graphical models via spectral sparsification
Dehua Cheng, Yu Cheng, Yan Liu, Richard Peng, and Shang-Hua Teng · 2015
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Daniel A. Spielman and Shang-Hua Teng · 2011
Cited alongside, same era.
Matrix analysis
Roger A Horn and Charles R Johnson · 2012
Cited alongside, same era.
User-friendly tail bounds for sums of random matrices
Joel A. Tropp · 2012
Cited alongside, same era.
Lx = b laplacian solvers and their algorithmic applications, 2012
N. K. Vishnoi · 2012
Cited alongside, same era.
Multiplying matrices faster than coppersmith-winograd
Virginia Vassilevska Williams · 2012
Cited alongside, same era.
Computing the log-determinant of symmetric, diagonally dominant matrices in near-linear time
Timothy Hunter, Ahmed El Alaoui, and Alexandre M. Bayen · 2014
Cited alongside, same era.
Computing the log-determinant of symmetric, diagonally dominant matrices in near-linear time
Timothy Hunter, Ahmed El Alaoui, and Alexandre M. Bayen · 2014
Cited alongside, same era.
Michael B. Cohen and Richard Peng · 2015
Later among the works it cites.
Large-scale log-determinant computation through stochastic chebyshev expansions
Insu Han, Dmitry Malioutov, and Jinwoo Shin · 2015
Later among the works it cites.
Fast generation of random spanning trees and the effective resistance metric
Aleksander Madry, Damian Straszak, and Jakub Tarnawski · 2015
Later among the works it cites.
Nearly tight oblivious subspace embeddings by trace inequalities
Michael B Cohen · 2016
Later among the works it cites.
Sampling random spanning trees faster than matrix multiplication
David Durfee, Rasmus Kyng, John Peebles, Anup B. Rao, and Sushant Sachdeva · 2016
Later among the works it cites.
Generating random spanning trees via fast matrix multiplication
Nicholas J. A. Harvey and Keyulu Xu · 2016
Later among the works it cites.
Sparsified cholesky and multigrid solvers for connection laplacians
Rasmus Kyng, Yin Tat Lee, Richard Peng, Sushant Sachdeva, and Daniel A Spielman · 2016
Later among the works it cites.
Almost-linear-time algorithms for markov chains and new spectral primitives for directed graphs
Michael B. Cohen, Jonathan A. Kelner, John Peebles, Richard Peng, Anup Rao, Aaron Sidford, and Adrian Vladu · 2017
Closest in time.
Density independent algorithms for sparsifying k-step random walks
Gorav Jindal, Pavel Kolev, Richard Peng, and Saurabh Sawlani · 2017
Closest in time.