Abstract: A spanner is a sparse subgraph that preserves pairwise distances within some pre-specified dilation. We describe a simple randomized algorithm for constructing a family of optimal sized stretch 2k-1 spanner of weighted graphs that runs in linear expected time. The underlying construction and techniques are quite elementary and accessible even to upper level undergraduate students. Joint work with Surender Baswana.
In the second part of my presentation, I would like to briefly highlight some opportunities in SNU for aspiring faculty candidates and other academic collaborations. SNU is an upcoming multidisciplinary private university that has been recently accorded the status of Institute of Eminence (IOE), a very selective cohort and well equipped to take on the challenges of India's New Education Policy 2020.
Bio: Sandeep Sen obtained his PhD from Duke university in 1989 and after a brief stint in Bell Labs, Murray Hill, was on the faculty of Computer Science dept in IIT Delhi till very recently. He has been at Shiv Nadar Nadar University for the past 3 years as Dean of School of Engineering. His research interests span Algorithms and Theoretical Computer Science and he is a Fellow of the Indian National Science Academy and the Indian Academy of Sciences.