Distinguished Seminar: Towards Universally Optimal Sorting Algorithms

Abstract: Algorithm design and analysis has been primarily guided by the measure of worst-case complexity for many reasons including robustness, ease of composing them, and also well-understood guarantees. On the other hand, it has also been criticized for being narrow and single-track in its evaluation of efficiency of algorithms on a large class of inputs. Sometimes, the worst-case scenarios are considered as exceptions in which case, we may be missing out on the performance of more commonly occurring inputs. Average case analysis require assumptions about the input distribution that are not known or measurable.

We consider a measure called universal complexity/optimality that can address this gap, albeit, more difficult to achieve, has been gaining some traction. Further, we will try to relate this to a class of algorithms known as oblivious algorithms that could be a useful paradigm for attaining universal optimality. We will illustrate this using some simple examples but far from any general theory.

Speaker Bio: Professor Sandeep Sen is a senior Computer Scientist whose research interests lie in the areas of Algorithms and Theoretical Computer Science. His focus areas include randomized algorithms, dynamic graph algorithms, geometric algorithms and approximation, and memory hierarchy models where several of his algorithms are among the best known in the literature for the corresponding problems.

Prior to joining Ashoka University, he was a Professor of CSE in IIT Delhi where he held Chair positions and served in leadership roles like Head of the Department and Dean of Faculty. He had also been Dean, the School of Engineering in SNIOE.

Professor Sen had several stints in Industry research laboratories like Bell Laboratories, IBM Research and MSR. He holds a Ph.D. from Duke University, an M.S. in Computer Engineering from the University of California, Santa Barbara, and a B.Tech. in CSE from IIT Kharagpur. He is a fellow of the Indian Academy of Sciences and the Indian National Science Academy.