9 citations · 42 across the 19 of their papers we have counts for
4 papers · 1 filter
Time-Biased Random Walks and Robustness of Expanders
Sam Olesker-Taylor, Thomas Sauerwald, John Sylvester
Random walks on expanders play a crucial role in Markov Chain Monte Carlo algorithms, derandomization, graph theory, and distributed computing. A desirable property is that they ar…
Mean-Biased Processes for Balanced Allocations
Dimitrios Los, Thomas Sauerwald, John Sylvester
We introduce a new class of balanced allocation processes which bias towards underloaded bins (those with load below the mean load) either by skewing the probability by which a bin…
Cover and Hitting Times of Hyperbolic Random Graphs
Marcos Kiwi, Markus Schepers, John Sylvester
We study random walks on the giant component of Hyperbolic Random Graphs (HRGs), in the regime when the degree distribution obeys a power law with exponent in the range . In…
The Cover Time of a (Multiple) Markov Chain with Rational Transition Probabilities is Rational
John Sylvester
The cover time of a Markov chain on a finite state space is the expected time until all states are visited. We show that if the cover time of a discrete-time Markov chain with rati…