Tata Institute of Fundamental Research
Constructive Proofs of Concentration Bounds
STCS Student Seminar
Speaker:
Ashutosh Singh (TIFR)
Organiser:
Varun Ramanathan
Date:
Friday, 10 Nov 2023, 16:00 to 17:30
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
We will see a combinatorial proof of the Chernoff-Hoeffding bound, which says that the sum of independent {0,1}-valued random variables is highly concentrated around the expected value. We will also see proof for the case of [0,1]-valued random variables. This is based upon the work of Russell Impagliazzo, Valentine Kabanets, Wolfgang Mulzer, and Natalia Shenkman.
| Speaker: | Ashutosh Singh (TIFR) |
| Organiser: | Varun Ramanathan |
| Date: | Friday, 10 Nov 2023, 16:00 to 17:30 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
We will see a combinatorial proof of the Chernoff-Hoeffding bound, which says that the sum of independent {0,1}-valued random variables is highly concentrated around the expected value. We will also see proof for the case of [0,1]-valued random variables. This is based upon the work of Russell Impagliazzo, Valentine Kabanets, Wolfgang Mulzer, and Natalia Shenkman.