Combinatorics Seminar
When: Sunday, March 8, 10am
Where: Schreiber 309
Speaker: Ori Gurel-Gurevich (Microsoft Research)
Title: Choice-memory tradeoff in allocations
Abstract:
Consider the classical balls-and-bins setup: n balls are thrown
independently and uniformly into n bins. The most loaded bin then has
log n/log log n balls with high probability. What happens when instead
of throwing balls completely by random, there is an allocation
algorithm which is given k uniformly and independently selected bins
to choose from for the location of each ball? A well known result of
Azar, Broder, Karlin and Upfal states that one can then achieve a
maximal load of log_k log n, simply by putting the ball in the less
loaded of the k bins. In order to implement this simple algorithm, one
needs to keep track of the status of the entire array of n bins, which
naively requires about n bits of memory.
The problem of what can be achieved with less memory was
raised by Itai Benjamini. The main result in this talk is that, generally
speaking, there is a tradeoff between the number of choices, k, and
the memory, m. That is, when km is much larger than n
one can achieve a constant maximal load,
while for km much smaller than n
the maximal load quickly reaches the same order
of magnitude as in the completely random setting.
A key ingredient in the proofs of the lower bounds is a large
deviation inequality, which relates the sum of a sequence of bounded
dependent random variables with the sum of their conditional
expectations. This inequality may prove useful in other combinatorial
or algorithmic problems.
Joint work with Noga Alon and Eyal Lubetzky.