2009 Probability Seminar - 09

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 & Upfal states that one can then achieve a maximal load of log_k log n, simply by putting each ball in the less loaded of the k optional bins. In order to implement this simple algorithm, one needs to keep track of the status of the entire array of n bins, which 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>>n one can achieve a constant maximal load, while for km<