Tata Institute of Fundamental Research
How to Generate a Large String almost Uniformly at Random, with a Small Number of Coin Tosses?
Student Seminar
Speaker:
Girish Varma
Tata Institute of Fundamental Research
School of Technology and Computer Science
Homi Bhabha Road
Date:
Friday, 28 May 2010 (all day)
Venue:
A-212 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
Computer scientists devise randomized algorithms when they cannot find good deterministic ones. Then they try to decrease the randomness used and still try to prove that the algorithm answers correctly with high probability. They even hope to decrease the randomness used to a small amount that they can finally convert the randomized algorithm to a deterministic one. A critical tool for doing this is to generate a long string from a distribution close to uniform, using only a small random string. We will see how to do this using Epsilon Biased Probability Spaces and also construct more general objects called strings that are almost k-wise independent.
| Speaker: | Girish Varma Tata Institute of Fundamental Research School of Technology and Computer Science Homi Bhabha Road |
| Date: | Friday, 28 May 2010 (all day) |
| Venue: | A-212 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
Computer scientists devise randomized algorithms when they cannot find good deterministic ones. Then they try to decrease the randomness used and still try to prove that the algorithm answers correctly with high probability. They even hope to decrease the randomness used to a small amount that they can finally convert the randomized algorithm to a deterministic one. A critical tool for doing this is to generate a long string from a distribution close to uniform, using only a small random string. We will see how to do this using Epsilon Biased Probability Spaces and also construct more general objects called strings that are almost k-wise independent.