## 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.