Fetching the paper…
Reading the bibliography…
In this paper we show how to recover a spectral approximations to broad classes of structured matrices using only a polylogarithmic number of adaptive linear measurements to either the matrix or its inverse.
M-matrices as covariance matrices of multinormal distributions
Samuel Karlin and Yosef Rinott · 1983
Earlier work this paper cites.
Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
Daniel A. Spielman and Shang-Hua Teng · 2004
Earlier work this paper cites.
Solving elliptic finite element systems in near-linear time with support preconditioners
Erik G. Boman, Bruce Hendrickson, and Stephen A. Vavasis · 2008
Earlier work this paper cites.
Faster approximate lossy generalized flow via interior point algorithms
Samuel I. Daitch and Daniel A. Spielman · 2008
Earlier work this paper cites.
Graph sparsification by effective resistances
Daniel A. Spielman and Nikhil Srivastava · 2008
Earlier work this paper cites.
Faster generation of random spanning trees
Jonathan A. Kelner and Aleksander Madry · 2009
Earlier work this paper cites.
Approaching optimality for solving SDD linear systems
Ioannis Koutis, Gary L. Miller, and Richard Peng · 2010
Earlier work this paper cites.
The laplacian paradigm: Emerging algorithms for massive graphs
Shang-Hua Teng · 2010
Earlier work this paper cites.
Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs
Paul Christiano, Jonathan A. Kelner, Aleksander Madry, Daniel A. Spielman, and Shang-Hua Teng · 2011
Earlier work this paper cites.
A parallel approximation algorithm for positive semidefinite programming
Rahul Jain and Penghui Yao · 2011
Earlier work this paper cites.
A nearly-m log n time solver for SDD linear systems
Ioannis Koutis, Gary L. Miller, and Richard Peng · 2011
Earlier work this paper cites.
Towards an sdp-based approach to spectral methods: A nearly-linear-time algorithm for graph partitioning and decomposition
Lorenzo Orecchia and Nisheeth K. Vishnoi · 2011
Earlier work this paper cites.
A parallel approximation algorithm for mixed packing and covering semidefinite programs
Rahul Jain and Penghui Yao · 2012
Earlier work this paper cites.
OSNAP: faster numerical linear algebra algorithms via sparser subspace embeddings
Jelani Nelson and Huy L. Nguyen · 2012
Earlier work this paper cites.
Approximating the exponential, the lanczos method and an õ( m )-time spectral algorithm for balanced separator
Lorenzo Orecchia, Sushant Sachdeva, and Nisheeth K. Vishnoi · 2012
Earlier work this paper cites.
Faster and simpler width-independent parallel algorithms for positive semidefinite programming
Richard Peng and Kanat Tangwongsan · 2012
Earlier work this paper cites.
Multiplying matrices faster than coppersmith-winograd
Virginia Vassilevska Williams · 2012
Earlier work this paper cites.
A simple, combinatorial algorithm for solving SDD systems in nearly-linear time
Jonathan A. Kelner, Lorenzo Orecchia, Aaron Sidford, and Zeyuan Allen Zhu · 2013
Cited alongside, same era.
A new approach to computing maximum flows using electrical flows
Yin Tat Lee, Satish Rao, and Nikhil Srivastava · 2013
Cited alongside, same era.
Efficient accelerated coordinate descent methods and faster algorithms for solving linear systems
Yin Tat Lee and Aaron Sidford · 2013
Cited alongside, same era.
Iterative row sampling
Mu Li, Gary L. Miller, and Richard Peng · 2013
Cited alongside, same era.
Dehua Cheng, Yu Cheng, Yan Liu, Richard Peng, and Shang-Hua Teng · 2014
Cited alongside, same era.
Using optimization to obtain a width-independent, parallel, simpler, and faster positive SDP solver
Zeyuan Allen Zhu, Yin Tat Lee, and Lorenzo Orecchia · 2016
Later among the works it cites.
On sketching quadratic forms
Alexandr Andoni, Jiecao Chen, Robert Krauthgamer, Bo Qin, David P. Woodruff, and Qin Zhang · 2016
Later among the works it cites.
Faster algorithms for computing the stationary distribution, simulating random walks, and more
Michael B. Cohen, Jonathan A. Kelner, John Peebles, Richard Peng, Aaron Sidford, and Adrian Vladu · 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.
Approximate gaussian elimination for laplacians - fast, sparse, and simple
Rasmus Kyng and Sushant Sachdeva · 2016
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Michael B. Cohen, Rasmus Kyng, Gary L. Miller, Jakub W. Pachocki, Richard Peng, Anup B. Rao, and Shen Chen Xu · 2014
Cited alongside, same era.
Uniform sampling for matrix approximation
Michael B. Cohen, Yin Tat Lee, Cameron Musco, Christopher Musco, Richard Peng, and Aaron Sidford · 2014
Cited alongside, same era.
Single pass spectral sparsification in dynamic streams
Michael Kapralov, Yin Tat Lee, Cameron Musco, Christopher Musco, and Aaron Sidford · 2014
Cited alongside, same era.
An almost-linear-time algorithm for approximate max flow in undirected graphs, and its multicommodity generalizations
Jonathan A. Kelner, Yin Tat Lee, Lorenzo Orecchia, and Aaron Sidford · 2014
Cited alongside, same era.
Path finding methods for linear programming: Solving linear programs in õ(vrank) iterations and faster algorithms for maximum flow
Yin Tat Lee and Aaron Sidford · 2014
Cited alongside, same era.
An efficient parallel solver for SDD linear systems
Richard Peng and Daniel A. Spielman · 2014
Cited alongside, same era.
Estimation of positive definite m-matrices and structure learning for attractive gaussian markov random fields
Martin Slawski and Matthias Hein · 2014
Cited alongside, same era.
Aleksander Madry · 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 B. Rao, Aaron Sidford, and Adrian Vladu · 2017
Later among the works it cites.
Negative-weight shortest paths and unit capacity minimum cost flow in õ ( m 10/7 {}^{\mbox{10/7}} log W ) time (extended abstract)
Michael B. Cohen, Aleksander Madry, Piotr Sankowski, and Adrian Vladu · 2017
Later among the works it cites.
Matrix scaling and balancing via box constrained newton’s method and interior point methods
Michael B. Cohen, Aleksander Madry, Dimitris Tsipras, and Adrian Vladu · 2017
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 · 2017
Later among the works it cites.
Total positivity in markov structures
Shaun Fallat, Steffen Lauritzen, Kayvan Sadeghi, Caroline Uhler, Nanny Wermuth, and Piotr Zwiernik · 2017
Later among the works it cites.
An sdp-based algorithm for linear-sized spectral sparsification
Yin Tat Lee and He Sun · 2017
Later among the works it cites.
AmirMahdi Ahmadinejad, Arun Jambulapati, Amin Saberi, and Aaron Sidford · 2018
Closest in time.
Non-convex matrix completion against a semi-random adversary
Yu Cheng and Rong Ge · 2018
Closest in time.
Learning networks from random walk-based node similarities
Jeremy G. Hoskins, Cameron Musco, Christopher Musco, and Charalampos E. Tsourakakis · 2018
Closest in time.
An almost-linear time algorithm for uniform random spanning tree generation
Aaron Schild · 2018
Closest in time.