## Abstract

The main contribution of this work is a construction of a two-source extractor for quasi-logarithmic min-entropy. That is, an extractor for two independent n-bit sources with min-entropy Õ(log n), which is optimal up to the poly(log log n) factor. A strong motivation for constructing two-source extractors for low entropy is for Ramsey graphs constructions. Our two-source extractor readily yields a (log n)^{(log log log n)O(1)} -Ramsey graph on n vertices. Although there has been exciting progress towards constructing O(log n)-Ramsey graphs in recent years, a line of work that this paper contributes to, it is not clear if current techniques can be pushed so as to match this bound. Interestingly, however, as an artifact of current techniques, one obtains strongly explicit Ramsey graphs, namely, graphs on n vertices where the existence of an edge connecting any pair of vertices can be determined in time polylog n. On top of our strongly explicit construction, in this work, we consider algorithms that output the entire graph in poly(n)-time, and make progress towards matching the desired O(log n) bound in this setting. In our opinion, this is a natural setting in which Ramsey graphs constructions should be studied. The main technical novelty of this work lies in an improved construction of an independence-preserving merger (IPM), avariant of the well-studied notion of a merger, which was recently introduced by Cohen and Schulman. Our construction is based on a new connection to correlation breakers with advice. In fact, our IPM satisfies a stronger and more natural property than that required by the original definition, and we believe it may find further applications.

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

Title of host publication | STOC 2017 - Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing |

Editors | Pierre McKenzie, Valerie King, Hamed Hatami |

Publisher | Association for Computing Machinery |

Pages | 1157-1170 |

Number of pages | 14 |

ISBN (Electronic) | 9781450345286 |

DOIs | |

State | Published - Jun 19 2017 |

Event | 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017 - Montreal, Canada Duration: Jun 19 2017 → Jun 23 2017 |

### Publication series

Name | Proceedings of the Annual ACM Symposium on Theory of Computing |
---|---|

Volume | Part F128415 |

ISSN (Print) | 0737-8017 |

### Other

Other | 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017 |
---|---|

Country/Territory | Canada |

City | Montreal |

Period | 6/19/17 → 6/23/17 |

## All Science Journal Classification (ASJC) codes

- Software

## Keywords

- Multi-source extractors
- Non-malleable extractors
- Ramsey graphs