### DIMACS Theoretical Computer Science Seminar

Title: New explicit constructions of randomness extractors from weak
sources, and of bipartite Ramsey graphs

Speaker: **Guy Kindler**, DIMACS, Rutgers University

Date: March 29, 2005 2:00-3:00pm

Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:

Randomness is extensively used in theory and practice to speed up
algorithms, and to apply cryptographic primitives. In the analysis of
such algorithms we assume we have free access to random independent
and unbiased random bits, although this is not clearly the case in
real life (for example, in the cryptographic framework, consider the
case where some information about the source of randomness has been
revealed). It is therefore interesting to try to get pure random
independent bits out of weak sources of randomness.

We show an extractor that given access to three independent random
strings with unknown distributions, outputs truly random independent
bits by applying a deterministic polynomial time function to them. The
only constraint on the original sources is that their entropy rate is
at least an arbitrary positive constant r (the entropy rate of a
random string is, loosely speaking, the amount of randomness it has
per bit). This is the first known construction where the number of
sources required does not depend on the parameter r.

Using some more new ideas, we also provide explicit constructions of
bipartite Ramsey graphs. Given a parameter r<1, the problem is to find
explicit bipartite graphs on 2N vertices, such that no induced N^r by
N^r subgraph is a bipartite clique, nor is it an independent set. We
provide explicit constructions of bipartite Ramsey graphs for any
positive constant r, after for many years 1/2 was the best constant
for which such constructions were known.

Joint work with Boaz Barak, Benny Sudakov, Ronen Shaltiel and Avi
Wigderson.