83. Mathematical Colloquium
Michael Krivelevich
Tel Aviv University
INTELLIGENCE VS RANDOMNESS: THE POWER OF CHOICES
March 27, 2013, 12:30
room S4, 3rd floor
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 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 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. Models to be defined and discussed include the so called Achlioptas process and Ramsey-type games on random graphs.
About the speaker
Prof. Michael Krivelevich se narodil v Kaliningradu (Kralovci), studoval v Moskve, Haife a Tel Avivu (kde jeho skoliteli byli Ron Aharoni a Noga Alon) a zahy se proslavil svymi pracemi v oblasti nahodnych grafu. Jiz behem studia ziskal nekolik oceneni. Prednesl prednasky a hostoval na prednich mezinarodnich institucich (namatkou jmenujme ETH Zurich, IAS Princeton, UCLA, Carnegie Mellon University, DIMACS, and Berkeley). Od roku 2005 je radnym profesorem na Universite v Tel Avivu, kde v letech 2007-9 byl reditelem matematickeho ústavu. Krivelevich je autorem vice nez 150 vedeckych praci. V minulosti organizoval radu konferenci a je tez vedoucim redaktorem casopisu Electronic Journal of Combinatorics a clenem redakcnich rad dalsich tri casopisu. Z jeho vedecke prace zminme soubor praci venovanych kombinatoricke teorii her, kde patri k zakladatelum teto rychle se rozvijejici oblasti. Domnivam se, ze jeho prazske kolokvium toho bude dokladem.
