Title: The Magical Power of Coin-Tossing in Algorithm Design

Speaker: Sanjeev Khanna

Abstract:

It is intuitively clear that when an algorithm is given more time and more space, it can perform more powerful computations. But there is another resource that confers magical powers to algorithms, namely, having access to a fair coin. Such algorithms are called randomized algorithms, and they can often solve complex problems much faster and using very little space. As algorithms confront challenge of efficiently processing vast amounts of data, randomized algorithms have taken a center-stage and they sometimes allow us to solve a problem using time or space that is much smaller than even the size of the input data.

On surface, this appears counterintuitive -- after all, how could tossing a few coins could help an algorithm solve a complex computational problem? In this talk, I will show several examples that illustrate this magical power of randomized algorithms.