COL866: Special Topics in Algorithms
Topic: Concentration Inequalities and their Applications in Computer Science

II semester: 2022-23

Amitabha Bagchi

Class Timings: M Th 3:30PM-5PM.
Venue: SIT 006.

Course objectives

The purpose of this course is to discuss various inequalities that help bound the probability that a random variable, or sum of random variables, is far from its expected value. We will show how these inequalities are used in various area of computer science like algorithms, networks, and machine learning.


Background required: Elementary probability, some linear algebra.

If we have time left, and based on interest, we may also cover other topics. A dscussion of other possibilities will be held around the midpoint of the class.


Other references

Course calendar


Evaluation will be on the basis of 3-4 take-home exams.

Attendance policy

If your attendance is below 75% then your 4th take-home exam will not be graded.

Plagiarism policy

If you copy even a single line from anyone else's paper or any book, website, or any other source your score for the entire course will be set to 0.

Audit policy

Audit pass will be given if
Amitabha Bagchi