16
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      Two-Source Dispersers for Polylogarithmic Entropy and Improved Ramsey Graphs

      Preprint

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          In his 1947 paper that inaugurated the probabilistic method, Erd\H{o}s proved the existence of \(2\log{n}\)-Ramsey graphs on \(n\) vertices. Matching Erd\H{o}s' result with a constructive proof is 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 [Ann. Math'12], who constructed a \(2^{2^{(\log\log{n})^{1-\alpha}}}\)-Ramsey graph, for some small universal constant \(\alpha > 0\). In this work, we significantly improve the result of Barak~\etal and construct \(2^{(\log\log{n})^c}\)-Ramsey graphs, for some universal constant \(c\). In the language of theoretical computer science, our work resolves the problem of explicitly constructing two-source dispersers for polylogarithmic entropy.

          Related collections

          Author and article information

          Journal
          14 June 2015
          Article
          1506.04428
          efa24e0f-f9d0-4ead-a202-1fc5c381b53b

          http://arxiv.org/licenses/nonexclusive-distrib/1.0/

          History
          Custom metadata
          math.CO cs.CC cs.DM

          Comments

          Comment on this article

          Similar content270