Special Lecture: Lecture series on Randomized Algorithms – 5-9 Jan 2024
Type: Special Lecture – Special Lecture
Event Date: 05 Jan 2024
Venue: RKMVERI, Belur Main Campus
Campus: Belur Campus
Department: Computer Science

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:

Sl. No. Date Time
1 Friday, 5 Jan, 2024 3.00 PM to 4.30 PM
2 Saturday, 6 Jan, 2024 11:00 AM to 12:30 PM
3 Monday, 8 Jan, 2024 3.00 PM to 4.30 PM
4 Tuesday, 9 Jan, 2024 3.00 PM to 4.30 PM

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.

Activity Coordinator(s)
Faculty/Staff Name Details
Swami Punyeshwarananda (Primary Coordinator) Computer Science – Belur Campus
Participant Information
RKMVERI Faculty & Staff 5 (Male: 5, Female: 0)
RKMVERI Students 37 (Male: 37, Female: 0)

Leave a Reply

Your email address will not be published. Required fields are marked *