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.