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 be almost surely 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, where a limited manipulation of the otherwise truly random input is capable to advance significantly various goals. In this talk I will describe 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 way. Models to be defined and discussed include the Achlioptas process and Ramsey-type games on random graphs.

Tee/Kaffee/Gebäch
ab 13:45 Uhr,
Arnimallee 3, Raum 006