Entrywise Approximate Laplacian Solving
<|reference_start|>Entrywise Approximate Laplacian Solving: We study the escape probability problem in random walks over graphs. Given vertices, $s,t,$ and $p$, the problem asks for the probability that a random walk starting at $s$ will hit $t$ before hitting $p$. Such probabilities can be exponentially small even for unweighted undirected graphs with polynomial mixing time. Therefore current approaches, which are mostly based on fixed-point arithmetic, require $n$ bits of precision in the worst case. We present algorithms and analyses for weighted directed graphs under floating-point arithmetic and improve the previous best running times in terms of the number of bit operations. We believe our techniques and analysis could have a broader impact on the computation of random walks on graphs both in theory and in practice.<|reference_end|>
@article{chen2024entrywise,
    title={Entrywise Approximate Laplacian Solving},
    author={Jingbang Chen, Mehrdad Ghadiri, Hoai-An Nguyen, Richard Peng, Junzhao
  Yang},
    journal={arXiv preprint arXiv:2409.10022},
    year={2024},
    archivePrefix={arXiv},
    eprint={2409.10022},
    primaryClass={cs.DS}
}