83 KAM Mathematical Colloquium

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.
 

O přednášejícím

Prof. Michael Krivelevich se narodil v Kaliningradu (Kralovci), studoval v Moskvě, Haife a Tel Avivu (kde jeho školiteli byli Ron Aharoni a Noga Alon) a zahy se proslavil svými pracemi v oblasti náhodných grafů. Již během studia získal několik ocenění. Přednesl přednášky a hostoval na předních mezinárodních institucích (namátkou jmenujme ETH Zurich, IAS Princetown, UCLA, Carnegie Mellon University, DIMACS a Berkeley). Od roku 2005 je řádným profesorem na Universitě v Tel Avivu, kde v letech 2007-9 byl ředitelem matematického ústavu. Krivelevich je autorem více než 150 vědeckých prací. V minulosti organizoval řadu konferencí a je též vedoucím redaktorem časopisu Electronic Journal of Combinatorics a clenem redakčních rad dalších tří časopisů. Z jeho vědecké práce zmiňme soubor prací věnovaných kombinatorické teorii her, kde patří k zakladatelům této rychle se rozvíjející oblasti.