36 citations · 118 across the 28 of their papers we have counts for
8 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…
An Improved Drift Theorem for Balanced Allocations
Dimitrios Los, Thomas Sauerwald
In the balanced allocations framework, there are jobs (balls) to be allocated to servers (bins). The goal is to minimize the gap, the difference between the maximum and the…
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…
Random walks on randomly evolving graphs
Leran Cai, Thomas Sauerwald, Luca Zanetti
A random walk is a basic stochastic process on graphs and a key primitive in the design of distributed algorithms. One of the most important features of random walks is that, under…
Random Walks on Dynamic Graphs: Mixing Times, HittingTimes, and Return Probabilities
Thomas Sauerwald, Luca Zanetti
We establish and generalise several bounds for various random walk quantities including the mixing time and the maximum hitting time. Unlike previous analyses, our derivations are…
Intersection and mixing times for reversible chains
Yuval Peres, Thomas Sauerwald, Perla Sousi +1
Suppose X and Y are two independent irreducible Markov chains on n states. We consider the intersection time, which is the first time their trajectories intersect. We show for reve…