Please note: This PhD seminar will take place in DC 2306 and online.
Jingbang Chen, PhD candidate
David R. Cheriton School of Computer Science
Supervisors: Professors Lap Chi Lau, Richard Peng
We will be discussing a joint work with Mehrdad Ghadiri, Hoai-An Nguyen, Richard Peng, Junzhao Yang.
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.
To join this PhD seminar in person, please go to DC 2306. You can also attend virtually using Zoom.