Fetching the paper…
Reading the bibliography…
Graph sparsification underlies a large number of algorithms, ranging from approximation algorithms for cut problems to solvers for linear systems in the graph Laplacian.
New notions and constructions of sparsification for graphs and hypergraphs
Nikhil Bansal, Ola Svensson, and Luca Trevisan · 1905
Earlier work this paper cites.
Quantum and classical algorithms for approximate submodular function minimization
Yassine Hamoudi, Patrick Rebentrost, Ansis Rosmanis, and Miklos Santha · 1907
Earlier work this paper cites.
Near-optimal approximate discrete and continuous submodular function minimization
Brian Axelrod, Yang P. Liu, and Aaron Sidford · 1909
Earlier work this paper cites.
Quantum walk search algorithms and effective resistance
Stephen Piddock · 1912
Earlier work this paper cites.
Bounds for the quantity of information transmitted by a quantum communication channel
Alexander S. Holevo · 1973
Earlier work this paper cites.
Max cut and the smallest eigenvalue
Luca Trevisan · 1978
Earlier work this paper cites.
Universal classes of hash functions
Lawrence J. Carter and Mark N. Wegman · 1979
Earlier work this paper cites.
Spectra of graphs
Dragoš M. Cvetkovic, Michael Doob, and Horst Sachs · 1980
Earlier work this paper cites.
Selected applications of minimum cuts in networks
Jean-Claude Picard and Maurice Queyranne · 1982
Earlier work this paper cites.
Covering problems for Markov chains
Peter Matthews · 1988
Earlier work this paper cites.
On sparse spanners of weighted graphs
Ingo Althöfer, Gautam Das, David Dobkin, Deborah Joseph, and José Soares · 1993
Earlier work this paper cites.
Using randomized sparsification to approximate minimum cuts
David R. Karger · 1994
Earlier work this paper cites.
Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
Michel X. Goemans and David P. Williamson · 1995
Earlier work this paper cites.
Approximating s − t s-t minimum cuts in O ~ ( n 2 ) \widetilde{O}(n^{2}) time
András A. Benczúr and David R. Karger · 1996
Earlier work this paper cites.
The electrical resistance of a graph captures its commute and cover times
Ashok K. Chandra, Prabhakar Raghavan, Walter L. Ruzzo, Roman Smolensky, and Prasoon Tiwari · 1996
Earlier work this paper cites.
Combinatorial preconditioners for sparse, symmetric, diagonally dominant linear systems
Keith D. Gremban · 1996
Earlier work this paper cites.
A fast quantum mechanical algorithm for database search
Lov K. Grover · 1996
Earlier work this paper cites.
Spectral graph theory
Fan R.K. Chung · 1997
Earlier work this paper cites.
Approximation algorithms for np-hard problems
David B. Shmoys · 1997
Earlier work this paper cites.
The anatomy of a large-scale hypertextual web search engine
Sergey Brin and Lawrence Page · 1998
Earlier work this paper cites.
Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
Tom Leighton and Satish Rao · 1999
Earlier work this paper cites.
Minimum cuts in near-linear time
David R. Karger · 2000
Earlier work this paper cites.
The cover time, the blanket time, and the Matthews bound
Jeff Kahn, Jeong Han Kim, Laszlo Lovasz, and Van H. Vu · 2000
Earlier work this paper cites.
Distributed computing
David Peleg · 2000
Earlier work this paper cites.
Quantum lower bounds by polynomials
Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf · 2001
Earlier work this paper cites.
Reducibility among combinatorial problems
Richard M. Karp · 2001
Earlier work this paper cites.
Property testing in bounded degree graphs
Oded Goldreich and Dana Ron · 2002
Earlier work this paper cites.
Quantum computation and quantum information
Michael A. Nielsen and Isaac Chuang · 2002
Earlier work this paper cites.
On spectral clustering: Analysis and an algorithm
Andrew Y. Ng, Michael I. Jordan, and Yair Weiss · 2002
Earlier work this paper cites.
Semi-supervised learning using Gaussian fields and harmonic functions
Xiaojin Zhu, Zoubin Ghahramani, and John D. Lafferty · 2003
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.
Approximate distance oracles
Mikkel Thorup and Uri Zwick · 2005
Earlier work this paper cites.
Learning from labeled and unlabeled data on a directed graph
Dengyong Zhou, Jiayuan Huang, and Bernhard Schölkopf · 2005
Earlier work this paper cites.
Quantum query complexity of some graph problems
Christoph Dürr, Mark Heiligman, Peter Høyer, and Mehdi Mhalla · 2006
Earlier work this paper cites.
Sampling algorithms for l 2 l_{2} regression and applications
Petros Drineas, Michael W. Mahoney, and Shan Muthukrishnan · 2006
Earlier work this paper cites.
Spectral partitioning works: Planar graphs and finite element meshes
Daniel A. Spielman and Shang-Hua Teng · 2006
Earlier work this paper cites.
Quantum clustering algorithms
Esma Aïmeur, Gilles Brassard, and Sébastien Gambs · 2007
Cited alongside, same era.
Negative weights make adversaries stronger
Peter Høyer, Troy Lee, and Robert Spalek · 2007
Cited alongside, same era.
Optimal inapproximability results for MAX-CUT and other 2-variable CSPs?
Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O’Donnell · 2007
Cited alongside, same era.
Iordanis Kerenidis and Jonas Landman · 2007
Cited alongside, same era.
A tutorial on spectral clustering
Ulrike von Luxburg · 2007
Cited alongside, same era.
Quantum property testing
Harry Buhrman, Lance Fortnow, Ilan Newman, and Hein Röhrig · 2008
Quantum algorithms for nearest-neighbor methods for supervised and unsupervised learning
Nathan Wiebe, Ashish Kapoor, and Krysta Svore · 2015
Later among the works it cites.
Secure identity-based encryption in the quantum random oracle model
Mark Zhandry · 2015
Later among the works it cites.
Alexandr Andoni, Jiecao Chen, Robert Krauthgamer, Bo Qin, David P. Woodruff, and Qin Zhang · 2016
Later among the works it cites.
A combinatorial, primal-dual approach to semidefinite programs
Sanjeev Arora and Satyen Kale · 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
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
Expander flows, geometric embeddings and graph partitioning
Sanjeev Arora, Satish Rao, and Umesh Vazirani · 2009
Cited alongside, same era.
Quantum algorithm for linear systems of equations
Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd · 2009
Cited alongside, same era.
Jonah Sherman · 2009
Cited alongside, same era.
Introduction to testing graph properties
Oded Goldreich · 2010
Cited alongside, same era.
The Laplacian paradigm: Emerging algorithms for massive graphs
Shang-Hua Teng · 2010
Cited alongside, same era.
Quantum complexity of minimum cut
Simon Apers and Troy Lee · 2011
Cited alongside, same era.
Later among the works it cites.
Faster spectral sparsification and numerical algorithms for SDD matrices
Ioannis Koutis, Alex Levin, and Richard Peng · 2016
Later among the works it cites.
Simple parallel and distributed algorithms for spectral graph sparsification
Ioannis Koutis and Shen Chen Xu · 2016
Later among the works it cites.
Approximate undirected maximum flows in O ( m polylog ( n ) ) O(m\,\mathrm{polylog}(n)) time
Richard Peng · 2016
Later among the works it cites.
Sparse sums of positive semidefinite matrices
Marcel K. Silva, Nicholas J. A. Harvey, and Cristiane M. Sato · 2016
Later among the works it cites.
Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
Andrew M. Childs, Robin Kothari, and Rolando D. Somma · 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.
Single pass spectral sparsification in dynamic streams
Michael Kapralov, Yin Tat Lee, Cameron M. Musco, Christopher P. Musco, and Aaron Sidford · 2017
Later among the works it cites.
Efficient quantum algorithms for analyzing large sparse electrical networks
Guoming Wang · 2017
Later among the works it cites.
Lower bounds for approximating graph parameters via communication complexity
Talya Eden and Will Rosenbaum · 2018
Later among the works it cites.
Quantum algorithms for connectivity and related problems
Michael Jarret, Stacey Jeffery, Shelby Kimmel, and Alvaro Piedrafita · 2018
Later among the works it cites.
Graph spanners: A tutorial review
Reyan Ahmed, Greg Bodwin, Faryad D. Sahneh, Keaton Hamm, Mohammad J.L. Jebelli, Stephen Kobourov, and Richard Spence · 2019
Closest in time.
On solving linear systems in sublinear time
Alexandr Andoni, Robert Krauthgamer, and Yosef Pogrow · 2019
Closest in time.
Hamiltonian sparsification and gap-simulation
Dorit Aharonov and Leo Zhou · 2019
Closest in time.
Faster quantum and classical SDP approximations for quadratic binary optimization
Fernando G. S. L. Brandão, Richard Kueng, and Daniel Stilck França · 2019
Closest in time.
Shantanav Chakraborty, András Gilyén, and Stacey Jeffery · 2019
Closest in time.
A general framework for graph sparsification
Wai-Shing Fung, Ramesh Hariharan, Nicholas J. A. Harvey, and Debmalya Panigrahi · 2019
Closest in time.
András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe · 2019
Closest in time.
Spectral sparsification of matrix inputs as a preprocessing step for quantum algorithms
Steven Herbert and Sathyawageeswar Subramanian · 2019
Closest in time.
Tsuyoshi Ito and Stacey Jeffery · 2019
Closest in time.
q-means: A quantum algorithm for unsupervised machine learning
Iordanis Kerenidis, Jonas Landman, Alessandro Luongo, and Anupam Prakash · 2019
Closest in time.
Spectral sparsification of hypergraphs
Tasuku Soma and Yuichi Yoshida · 2019
Closest in time.
Private communication, 2019
Luca Zanetti · 2019
Closest in time.
The quantum query complexity of composition with a relation
Aleksandrs Belovs and Troy Lee · 2020
Closest in time.
Quantum spectral clustering through a biased phase estimation algorithm
Ammar Daskin · 2020
Closest in time.
A sublinear time quantum algorithm for st minimum cut on dense simple graphs
Simon Apers, Arinta Auza, and Troy Lee · 2021
Closest in time.
Chris Cade, Farrokh Labib, and Ido Niesen · 2021
Closest in time.
Improved quantum lower and upper bounds for matrix scaling
Sander Gribling and Harold Nieuwboer · 2021
Closest in time.
Partitioning well-clustered graphs: Spectral clustering works!
Richard Peng, He Sun, and Luca Zanetti · 2021
Closest in time.
Maximum flow and minimum-cost flow in almost-linear time
Li Chen, Rasmus Kyng, Yang P Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva · 2022
Closest in time.
Quantum algorithms and lower bounds for linear regression with norm constraints
Yanlin Chen and Ronald de Wolf · 2023
Closest in time.
Nearly maximum flows in nearly linear time
Jonah Sherman · 2077
Closest in time.