research
∙
08/21/2023
An Improved Drift Theorem for Balanced Allocations
In the balanced allocations framework, there are m jobs (balls) to be al...
share
research
∙
08/09/2023
Mean-Biased Processes for Balanced Allocations
We introduce a new class of balanced allocation processes which bias tow...
research
∙
02/09/2023
Balanced Allocations in Batches: The Tower of Two Choices
In balanced allocations, the goal is to place m balls into n bins, so as...
research
∙
01/24/2023
Balanced Allocations with Heterogeneous Bins: The Power of Memory
We consider the allocation of m balls (jobs) into n bins (servers). In t...
research
∙
06/15/2022
Balanced Allocations with the Choice of Noise
We consider the allocation of m balls (jobs) into n bins (servers). In t...
research
∙
04/08/2022
The Power of Filling in Balanced Allocations
It is well known that if m balls (jobs) are placed sequentially into n b...
research
∙
03/25/2022
Balanced Allocations in Batches: Simplified and Generalized
We consider the allocation of m balls (jobs) into n bins (servers). In t...
research
∙
03/23/2022
Tight Bounds for Repeated Balls-into-Bins
We study the repeated balls-into-bins process introduced by Becchetti, C...
research
∙
10/20/2021
Balanced Allocations: Caching and Packing, Twinning and Thinning
We consider the sequential allocation of m balls (jobs) into n bins (ser...
research
∙
07/08/2021
Balanced Allocations with Incomplete Information: The Power of Two Queries
We consider the problem of allocating m balls into n bins with incomplet...
research
∙
11/16/2020
Multiple Random Walks on Graphs: Mixing Few to Cover Many
Random walks on graphs are an essential primitive for many randomised al...
research
∙
06/18/2020
Random walks on randomly evolving graphs
A random walk is a basic stochastic process on graphs and a key primitiv...
research
∙
06/03/2020
Time Dependent Biased Random Walks
We study the biased random walk where at each step of a random walk a "c...
research
∙
11/12/2019
The Power of Two Choices for Random Walks
We apply the power-of-two-choices paradigm to random walk on a graph: ra...
research
∙
03/04/2019
Random Walks on Dynamic Graphs: Mixing Times, HittingTimes, and Return Probabilities
We establish and generalise several bounds for various random walk quant...
research
∙
08/28/2018