83 KAM Mathematical Colloquium
Michael Krivelevich
Tel Aviv University
INTELLIGENCE VS RANDOMNESS: THE POWER OF CHOICES
středa 27. března 2013 ve 12:30, posluchárna S4, třetí patro
KAM MFF UK
Malostranské nám. 25
118 00 Praha 1
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 seminal paper of Azar, Broder, Karlin and Upfal from 1994 - an exponential improvement!The above described result is just one manifestation of 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 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 certain predefined, and rather limited, way. Models to be defined and discussed include the so called Achlioptas process and Ramsey-type games on random graphs.
