Abstract: Consider the following very standard experiment: n balls are thrown independently at random each into n bins (if you are practically inclined, think about distributing n jobs at random between n machines). It is quite easy to see that the maximum load over all bins will typically be about ln n/lnln n. If however each ball is allowed to choose between two randomly drawn bins, the typical maximum bin load drops dramatically to about lnln n, as shown in a seminal paper of Azar, Broder, Karlin and Upfal from 1994 - an exponential improvement!

The above described result is just one manifestation of a recently widely studied phenomenon: a limited manipulation of the otherwise truly random input is frequently capable to advance various goals significantly. In this talk I will discuss results of this type, mainly focusing on the so called controlled random graph processes, where at each stage an algorithm is presented with a collection of randomly drawn edges and is allowed to manipulate this collection in a certain predefined, and rather limited, way.

Coffee will be served at 12:00 before the lecture
at Schreiber building 006