How to Generate a Large String almost Uniformly at Random, with a Small Number of Coin Tosses?

by Mr Girish Varma (School of Technology and Computer Science)

Friday 28 May 2010, 14:15 → 15:15 Asia/Kolkata

A-212 (Colaba Campus)

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.