Endre Szemeredi's Random Structures and Algorithms

by Prof. Jaikumar Radhakrishnan (School of Technology and Computer Science, Tata Institute of Fundamental Research, Mumbai)

Wednesday 16 May 2012, 16:00 → 17:00 Asia/Kolkata

AG-66 (Colaba Campus)

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)