scientific article; zbMATH DE number 7559046

DOI10.4230/LIPIcs.ITCS.2019.3MaRDI QIDQ5090373

Robert Krauthgamer, Yosef Pogrow, Alexandr Andoni

Publication date: 18 July 2022

Full work available at URL: https://arxiv.org/abs/1809.02995

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

linear systemssublinear timeLaplacian solverrandomized linear algebra

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (4)

Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving ⋮ Approximating Matrix Eigenvalues by Subspace Iteration with Repeated Random Sparsification ⋮ Sublinear Algorithms for Local Graph-Centrality Estimation ⋮ A queueing network-based distributed Laplacian solver

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators
• Ramanujan graphs
• On approximating the eigenvalues of stochastic matrices in probabilistic logspace
• Exact Kolmogorov and total variation distances between some familiar discrete distributions
• Exponential separation of quantum and classical communication complexity
• Survey of local algorithms
• Local Computation of PageRank Contributions
• On Approximating the Stationary Distribution of Time-reversible Markov Chains
• Powers of tensors and fast matrix multiplication
• Expander graphs and their applications
• An Efficient Method for Generating Discrete Random Variables with General Distributions
• Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
• Using PageRank to Locally Partition a Graph
• Quantum Algorithm for Systems of Linear Equations with Exponentially Improved Dependence on Precision
• Multiscale Matrix Sampling and Sublinear-Time PageRank Computation
• Solving Local Linear Systems with Boundary Conditions Using Heat Kernel Pagerank
• Finding sparse cuts locally using evolving sets
• A quantum-inspired classical algorithm for recommendation systems
• Solving SDD linear systems in nearly m log ^1/2 n time
• Sparsified Cholesky and multigrid solvers for connection laplacians
• Lx = b
• Quantum one-way communication can be exponentially stronger than classical communication
• A Note on the Inversion of Matrices by Random Walks
• Graph Sparsification by Effective Resistances

This page was built for publication: