Fetching the paper…
Reading the bibliography…
In this paper we consider the problem of efficiently computing $\epsilon$-sketches for the Laplacian and its pseudoinverse.
J. Cheeger, “A lower bound for the smallest eigenvalue of the laplacian. problems in analysis,” in Princeton University Press
1970
Earlier work this paper cites.
Johns Hopkins University Press, 1996
G. H. Golub and C. F. V. Loan, Matrix computations (3. ed.) · 1996
Earlier work this paper cites.
D. A. Spielman and S. Teng, “Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems,” in SIAM Journal on Computing
2004
Earlier work this paper cites.
P. Drineas, M. W. Mahoney, and S. Muthukrishnan, “Relative-error c u r cur matrix decompositions,” in SIAM Journal on Matrix Analysis and Applications
2008
Earlier work this paper cites.
J. Batson, D. A. Spielman, and N. Srivastava, “Twice-ramanujan sparsifiers,” in Symposium on Theory of Computing
2009
Earlier work this paper cites.
J. A. Kelner and A. Madry, “Faster generation of random spanning trees,” in CoRR
2009
Earlier work this paper cites.
I. Koutis, G. L. Miller, and R. Peng, “Approaching optimality for solving SDD linear systems,” in 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA
2010
Earlier work this paper cites.
D. A. Spielman and S. Srivastava, “Graph sparsification by effective resistances,” in SIAM Journal of Computing
2011
Earlier work this paper cites.
J. Ding, J. R. Lee, and Y. Peres, “Cover times, blanket times, and majorizing measures,” in STOC
2011
Earlier work this paper cites.
P. Christiano, J. A. Kelner, A. Madry, D. A. Spielman, and S. Teng, “Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs,” in Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6-8 June 2011
2011
Earlier work this paper cites.
I. Koutis, G. L. Miller, and R. Peng, “A nearly-m log n time solver for SDD linear systems,” in IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22-25, 2011
2011
Earlier work this paper cites.
2012
Earlier work this paper cites.
J. Sherman, “Nearly maximum flows in nearly linear time,” in 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA
2013
Cited alongside, same era.
J. A. Kelner, L. Orecchia, A. Sidford, and Z. Allen Zhu, “A simple, combinatorial algorithm for solving SDD systems in nearly-linear time,” in Symposium on Theory of Computing Conference, STOC’13, Palo Alto, CA, USA, June 1-4, 2013
2013
Cited alongside, same era.
Y. T. Lee and A. Sidford, “Efficient accelerated coordinate descent methods and faster algorithms for solving linear systems,” in 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA
2013
Cited alongside, same era.
J. A. Kelner, Y. T. Lee, L. Orecchia, and A. Sidford, “An almost-linear-time algorithm for approximate max flow in undirected graphs, and its multicommodity generalizations,” in Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014
Y. T. Lee and H. Sun, “Constructing linear-sized spectral sparsification in almost-linear time,” in IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015
2015
Later among the works it cites.
M. Dinitz, R. Krauthgamer, and T. Wagner, “Towards resistance sparsifiers,” in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2015
2015
Later among the works it cites.
2015
Later among the works it cites.
Y. T. Lee and A. Sidford, “Efficient inverse maintenance and faster algorithms for linear programming,” in IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015
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…
2014
Cited alongside, same era.
R. Peng and D. A. Spielman, “An efficient parallel solver for SDD linear systems,” in Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014
2014
Cited alongside, same era.
F. L. Gall, “Powers of tensors and fast matrix multiplication,” in International Symposium on Symbolic and Algebraic Computation, ISSAC ’14, Kobe, Japan, July 23-25, 2014
2014
Cited alongside, same era.
2014
Cited alongside, same era.
S. Wang, “Sharpened error bounds for random sampling based ℓ 2 \ell_{2} regression,” in Unpublished
2014
Cited alongside, same era.
J. A. Kelner, Y. T. Lee, L. Orecchia, and A. Sidford, “An almost-linear-time algorithm for approximate max flow in undirected graphs, and its multicommodity generalizations,” in Symposium on Discrete Algorithms
2014
Cited alongside, same era.
N. Anari and S. O. Gharan, “Effective-resistance-reducing flows, spectrally thin trees, and asymmetric TSP,” in IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015
2015
Cited alongside, same era.
Z. Allen Zhu, Z. Liao, and L. Orecchia, “Spectral sparsification and regret minimization beyond matrix multiplicative updates,” in Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015
2015
Cited alongside, same era.
A. Andoni, J. Chen, B. Krauthgamer, R. Qin, D. P. Woodruff, and Q. Zhang, “On sketching quadratic forms,” Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science
2016
Later among the works it cites.
I. Koutis and S. C. Xu, “Simple parallel and distributed algorithms for spectral graph sparsification,” in TOPC
2016
Later among the works it cites.
R. Kyng and S. Sachdeva, “Approximate gaussian elimination for laplacians - fast, sparse, and simple,” in IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA
2016
Later among the works it cites.
Y. T. Lee and H. Sun, “An sdp-based algorithm for linear-sized spectral sparsification,” in Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing
2017
Closest in time.
D. Durfee, R. Kyng, J. Peebles, A. B. Rao, and S. Sachdeva, “Sampling random spanning trees faster than matrix multiplication,” in STOC
2017
Closest in time.
K. G. Larsen and J. Nelson, “Optimality of the johnson-lindenstrauss lemma,” in IEEE 58th Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, 14-17 October, 2017
2017
Closest in time.
M. B. Cohen, J. A. Kelner, J. Peebles, R. Peng, A. B. Rao, A. Sidford, and A. Vladu, “Almost-linear-time algorithms for markov chains and new spectral primitives for directed graphs,” in STOC
2017
Closest in time.