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 << 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.