Endre Szemeredi's Random Structures and Algorithms

John Barretto
Wednesday, 16 May 2012, 16:00 to 17:00
AG-66 (Lecture Theatre)
Endre Szemeredi will receive the 2012 Abel Prize for his achievements in Discrete Mathematics. We will give a brief introduction to the area of Ramsey Theory, and discuss two themes in theoretical computer science related to Endre Szemeredi's work.
-- Should tables be sorted?
-- How to recycle random bits?
No advance knowledge of discrete mathematics or computer science will be expected of the audience. The material will be accessible to a general scientific audience.
(A popular article by R Ramachandran with the title Endre Szemeredi, A Hungarian Gem appeared recently in the magazine Frontline; this article is available here: http://www.frontlineonnet.com/fl2907/stories/20120420290709800.htm)