Multiplicative Approximations of Random Walk Transition Probabilities

DOI10.1007/978-3-642-22935-0_23MaRDI QIDQ3088100zbMATH OpenOpenAlexFDO

Authors Michael Kapralov, Rina Panigrahy

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

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

Recommendations

• Random walks relative to multiple transition matrices
• Exact and asymptotic properties of multistate random walks
• Transition probability estimates for long range random walks
• Random walks with occasionally modified transition probabilities
• Random walks with non-convolution equivalent increments and their applications
• Transition probability estimates for subordinate random walks
• scientific article; zbMATH DE number 3905592
• First-passage exponents of multiple random walks
• Random walks with similar transition probabilities

Cites work

• (1 + εΒ) -spanner constructions for general graphs
• A fast and efficient algorithm for low-rank approximation of a matrix
• A Survey on PageRank Computing
• All-Pairs Almost Shortest Paths
• Approximate distance oracles
• Deeper Inside PageRank
• Estimating PageRank on graph streams
• Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
• Fast Monte Carlo Algorithms for Matrices I: Approximating Matrix Multiplication
• Fast monte-carlo algorithms for finding low-rank approximations
• scientific article; zbMATH DE number 2038725 (Why is no real title available?)
• Low rank matrix-valued Chernoff bounds and approximate matrix multiplication
• Monte Carlo Methods in PageRank Computation: When One Iteration is Sufficient
• Numerical linear algebra in the streaming model
• Spanners and emulators with sublinear distance errors

Cited in

(4)

• Plans of multidimensional random walks allowing factorization of the transition probabilities
• Density independent algorithms for sparsifying k-step random walks
• Deterministic approximation of random walks in small space
• Transition probability estimates for subordinate random walks

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3088100)