Towards optimal two-source extractors and ramsey graphs

Gil Cohen

Research output: Chapter in Book/Report/Conference proceedingConference contribution

17 Scopus citations

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 languageEnglish (US)
Title of host publicationSTOC 2017 - Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing
EditorsPierre McKenzie, Valerie King, Hamed Hatami
PublisherAssociation for Computing Machinery
Pages1157-1170
Number of pages14
ISBN (Electronic)9781450345286
DOIs
StatePublished - Jun 19 2017
Event49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017 - Montreal, Canada
Duration: Jun 19 2017Jun 23 2017

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
VolumePart F128415
ISSN (Print)0737-8017

Other

Other49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017
Country/TerritoryCanada
CityMontreal
Period6/19/176/23/17

All Science Journal Classification (ASJC) codes

  • Software

Keywords

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

Fingerprint

Dive into the research topics of 'Towards optimal two-source extractors and ramsey graphs'. Together they form a unique fingerprint.

Cite this