A lecture series on ‘Randomized Algorithms’ was organized starting from Friday, 5 January 2024 in MB207, Medha Bhavan. The schedule of these talks is as follows:

Randomized algorithms are a fascinating class of algorithms whose applications can be seen in various fields such as machine learning, risk analysis, robotics, and cryptography, just to name a few. These talks are tailored to suit the audience who are new to randomized algorithms. They were delivered by Prof. Sumit Ganguly, a distinguished faculty member from the Department of Computer Science and Engineering, IIT Kanpur. An abstract of this lecture series is given below.

Some Examples of Tools and Techniques for Randomized Algorithms
In these sequence of talks, we tried to give an introductory tour of the general tools and techniques that are used for the analysis of randomized algorithms and illustrate it with a few well-known examples drawn from the domain of streaming algorithms.

We began with an overview of the basic techniques for obtaining tail concentration bounds, namely, the Chebychev inequality, the dth moment method, and the exponential moments method. As an application of the exponential moment method, we derived the Chernoff-Hoeffding bounds. We drew an example application from the domain of streaming algorithms, and used it as an example to illustrate the use of Chernoff-Hoeffding bound, Chebychev inequality and the dth moment method.

The example we considered was the problem of estimating the number of distinct elements in a rapidly arriving stream of items, to within an accuracy of factor (1 +/- epsilon) and confidence of 1-delta. The Chernoff’s bound application was used to analyze an algorithm based on the sampling/subsampling approach, which is by now classical. The dth moment method was used to analyze Knuth’s algorithm [2023]. An alternative Chernoff bound based analysis was also done for Knuth’s algorithm.