## Abstract

The main contribution of this work is an explicit construction of extractors for near logarithmic min-entropy. For any δ > 0 we construct an extractor for O(1/δ) n-bit sources with min-entropy (logn)1+δ. This is most interesting when δ is set to a small constant, though the result also yields an extractor for O(log logn) sources with logarithmic min-entropy. Prior to this work, the best explicit extractor in terms of supporting least-possible min-entropy, due to Li (FOCS'15), requires min-entropy (logn)2+δ from its O(1/δ) sources. Further, all current techniques for constructing multi-source extractors 'break' below min-entropy (log n)2. In fact, existing techniques do not provide even a disperser for o(log n) sources each with min-entropy (log n)1.99. Apart from being a natural problem, supporting logarithmic min-entropy has applications to combinatorics. A two-source disperser, let alone an extractor, for min-entropy O(log n) induces a (log, nO(1))-Ramsey graph on n vertices. Thus, constructing such dispersers would be a significant step towards constructively matching Erds' proof for the existence of (2log n)-Ramsey graphs on n vertices. Our construction does not rely on the sophisticated primitives that were key to the substantial recent progress on multi-source extractors, such as non-malleable extractors, correlation breakers, the lightest-bin condenser, or extractors for non-oblivious bit-fixing sources, although some of these primitives can be combined with our construction so to improve the output length and the error guarantee. Instead, at the heart of our construction is a new primitive called an independence-preserving merger. The construction of the latter builds on the alternating extraction technique.

Original language | English (US) |
---|---|

Title of host publication | Proceedings - 57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016 |

Publisher | IEEE Computer Society |

Pages | 178-187 |

Number of pages | 10 |

ISBN (Electronic) | 9781509039333 |

DOIs | |

State | Published - Dec 14 2016 |

Event | 57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016 - New Brunswick, United States Duration: Oct 9 2016 → Oct 11 2016 |

### Publication series

Name | Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS |
---|---|

Volume | 2016-December |

ISSN (Print) | 0272-5428 |

### Other

Other | 57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016 |
---|---|

Country/Territory | United States |

City | New Brunswick |

Period | 10/9/16 → 10/11/16 |

## All Science Journal Classification (ASJC) codes

- General Computer Science

## Keywords

- Correlation breakers
- Extractors
- Independence-preserving mergers