Prof. Sandeep Sen ,

Indian Institute of Technology, Dellhi,

India

Professor Sandeep Sen obtained his BTech in CS from IIT Kharagpur, MS from UC Santa Barbara and PhD from Duke University in 1989. After a brief stint in Bell Labs, Murray Hill, he has been a faculty in IIT Delhi since 1991. He has held Visiting positions in UNC Chapel Hill, Univ of Connecticut, MPI Saarbrucken, BRICS and MSR Bangalore and ISI Kolkata. His research interests span Algorithms and Complexity. Prof Sen is a Fellow of the Indian Academy of Sciences and the Indian National Science Academy. He is a former Head of Dept of CSE and presently Dean Faculty in IIT Delhi.

Title: Randomized techniques in algorithm design

We review some classical applications of random sampling techniques to fundamental problems in algorithm design and combinatorics. We present a simple linear time algorithm for weighted graph spanners that achieve optimal size