Multiplicative Approximations of Random Walk Transition Probabilities

DOI10.1007/978-3-642-22935-0_23zbMath1343.68118OpenAlexW2294664282MaRDI QIDQ3088100

Rina Panigrahy, Michael Kapralov

Publication date: 17 August 2011

Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-22935-0_23

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Random walks on graphs (05C81)

Cites Work

• Unnamed Item
• Estimating PageRank on graph streams
• Spanners and emulators with sublinear distance errors
• Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
• Deeper Inside PageRank
• All-Pairs Almost Shortest Paths
• Numerical linear algebra in the streaming model
• A fast and efficient algorithm for low-rank approximation of a matrix
• (1 + εΒ) -spanner constructions for general graphs
• Approximate distance oracles
• Low Rank Matrix-Valued Chernoff Bounds and Approximate Matrix Multiplication
• Monte Carlo Methods in PageRank Computation: When One Iteration is Sufficient
• Fast monte-carlo algorithms for finding low-rank approximations
• Fast Monte Carlo Algorithms for Matrices I: Approximating Matrix Multiplication
• A Survey on PageRank Computing

This page was built for publication: Multiplicative Approximations of Random Walk Transition Probabilities