Two-source dispersers for polylogarithmic entropy and improved Ramsey graphs

Gil Cohen

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

16 Scopus citations

Abstract

In his influential 1947 paper that inaugurated the probabilistic method, Erdos proved the existence of 2 log n-Ramsey graphs on n vertices. Matching Erdos' result with a constructive proof is considered a central problem in combinatorics, that has gained a significant attention in the literature. The state of the art result was obtained in the celebrated paper by Barak, Rao, Shaltiel, and Wigderson who constructed a 22(log log n)1-α-Ramsey graph, for some small universal constant α > 0. In this work, we significantly improve this result and construct 2(log logn)c-Ramsey graphs, for some universal constant c. In the language of theoretical computer science, this resolves the problem of explicitly constructing dispersers for two n-bit sources with entropy polylog(n). In fact, our disperser is a zero-error disperser that outputs a constant fraction of the entropy. Prior to this work, such dispersers could only support entropy Ω(n).

Original languageEnglish (US)
Title of host publicationSTOC 2016 - Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing
EditorsYishay Mansour, Daniel Wichs
PublisherAssociation for Computing Machinery
Pages278-284
Number of pages7
ISBN (Electronic)9781450341325
DOIs
StatePublished - Jun 19 2016
Event48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016 - Cambridge, United States
Duration: Jun 19 2016Jun 21 2016

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
Volume19-21-June-2016
ISSN (Print)0737-8017

Other

Other48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016
CountryUnited States
CityCambridge
Period6/19/166/21/16

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Explicit constructions
  • Ramsey graphs
  • Zero-error dispersers

Fingerprint Dive into the research topics of 'Two-source dispersers for polylogarithmic entropy and improved Ramsey graphs'. Together they form a unique fingerprint.

  • Cite this

    Cohen, G. (2016). Two-source dispersers for polylogarithmic entropy and improved Ramsey graphs. In Y. Mansour, & D. Wichs (Eds.), STOC 2016 - Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing (pp. 278-284). (Proceedings of the Annual ACM Symposium on Theory of Computing; Vol. 19-21-June-2016). Association for Computing Machinery. https://doi.org/10.1145/2897518.2897530