Theory Seminar: Schedule for Spring 2004

Nisheeth Vishnoi
Date: Friday, Jan 23rd, 2004.
Time: 2:00-3:00pm.
Room: CoC 109

Title: Deterministic Extractors for Almost Fixed Sources

Randomness has proved to be a powerful tool in Computer Science, Cryptography, Computational Mathematics and Optimization. Though randomized algorithms and protocols assume access to truly random bits, in practice, they use the output of "weak sources" of randomness such as pseudo-random number generators or physical sources. Hence it becomes important to study the following fundamental question pertaining to it (Extraction): How do we generate "high quality" random bits from "weak sources" for our applications? The (apparent) lack of natural sources producing high quality random bits motivates the problem of extracting almost true random bits from weak sources. This is not always achievable deterministically and one often needs (provably) access to a small, truly random seed. An important case in which deterministic extraction is possible is the so called "oblivious bit fixing source" An (n,k) oblivious bit fixing source (OBFS) is a weak random source that outputs n bits, out of which all but k random bits are fixed and the remaining are chosen independently and randomly. In this talk I will present a deterministic extraction scheme which outputs \Omega(log f(n)) random bits from any (n,f(n)) oblivious bit fixing source. The extractor is very simple and efficient. This improves on a result by Kamp and Zuckerman (FOCS 2003), who needed f(n)=\Omega(n^{1/2+\gamma}) to extract non-trivial randomness. This extractor construction also leads to a construction of almost independent set of random variables (in the spirit of Naor and Naor) deriving their randomness from an OBFS. This seems to be of independent interest. The analysis uses elementary properties of exponential sums from number theory. This is joint work with Dick Lipton.