TIME: 1:30-2:30 pm,  Tuesday, November 4, 2008

PLACE: CSE 503  

SPEAKER: Ariel Gabizon
         Simon Frasier University

TITLE: A Recycling Paradigm for Extracting many Random Bits


ABSTRACT: Randomness Extractors are algorithms which 'extract' random bits
from a `weak random source'.  A simple example of a weak random source is
a biased coin. An extractor for this source (which was given by Von-Neumann)
would be an algorithm that uses the biased coin tosses to produce unbiased
uniformly distributed bits.  Another example of a weak random source is
an (n,k)-bit-fixing source: A distribution on n bits that are all independent,
where some unknown subset of k bits is uniformly distributed, and the
other n-k bits are constants.  It is easy to see that taking the parity of
all bits gives a random bit.

In this talk we will survey some results on extracting randomness from
various types of sources For example, we show how to extract k-o(k) 
(almost) uniformly distributed bits from an (n,k)-bit-fixing source.
A central technique in our work is a 'recycling paradigm' which shows that
in certain situations we can use random bits already extracted from a source
to help us extract more bits from the same source.  An introduction to
randomness extractors will be given in the talk, so no prior knowledge
is necessary.

Based on joint works with Ran Raz and Ronen Shaltiel.