Computer Science/Discrete Mathematics Seminar I | |

Topic: | New Independent Source Extractors with Exponential Improvement |

Speaker: | Xin Li |

Affiliation: | University of Washington |

Date: | Monday, January 28 |

Time/Room: | 11:15am - 12:15pm/S-101 |

Video Link: | https://video.ias.edu/1213/csdm/0128-XinLi |

We study the problem of constructing extractors for independent weak random sources. The probabilistic method shows that such an extractor exists for two sources on n bits with min-entropy k >= 2 log n. On the other hand, explicit constructions are far from optimal. Previously the best known extractor for (n,k) sources requires O(log n/log k) independent sources [Rao06, Barak-Rao-Shaltiel-Wigderson06]. In this talk I will give a new extractor that uses only O(log (log n/log k))+O(1) independent sources. This improves the previous best result exponentially. The extractor is based on a new method for condensing somewhere random sources, which seems promising for further improvements.