2-source dispersers for n^o(1) entropy, and Ramsey graphs beating the Frankl-Wilson construction

Boaz Barak, Anup Rao, Ronen Shaltiel, Avi WigdersonAnnals 2012 · DOI

Abstract

The main result of this paper is an explicit disperser for two independent sources on $n$ bits, each of min-entropy $k = 2^{\log^\delta n}$, where $\delta < 1$ is some absolute constant. Put differently, setting $N = 2^n$ and $K = 2^k$, we construct an explicit $N \times N$ Boolean matrix for which no $K \times K$ sub-matrix is monochromatic. Viewed as the adjacency matrix of a bipartite graph, this gives an explicit construction of a bipartite $K$-Ramsey graph of $2N$ vertices. This improves the previous bound of $k = o(n)$ of Barak et al. As a corollary, we get a construction of a $2^{n^{o(1)}}$ (nonbipartite) Ramsey graph of $2^n$ vertices, significantly improving the previous bound of $2^{\tilde{O}(\sqrt{n})}$ due to Frankl and Wilson.

Introduction

Constructing explicit Ramsey graphs—graphs that contain neither large cliques nor large independent sets—has been a central challenge in combinatorics for over 70 years. While Paul Erdős used the probabilistic method in 1947 to prove that such graphs exist for very small $K$ (logarithmic in the number of vertices), finding an explicit, deterministic construction has proven remarkably difficult. For decades, the field was constrained by the "$\sqrt{n}$ barrier," where the best explicit constructions, such as the one by Frankl and Wilson (1981), could only guarantee $K = 2^{\tilde{O}(\sqrt{n})}$.

This paper, published in the Annals of Mathematics, represents a landmark achievement in theoretical computer science and combinatorics. By developing a novel "challenge-response" mechanism for 2-source dispersers, the authors provide the first explicit construction of Ramsey graphs that significantly beat the Frankl-Wilson bound, moving from $2^{\sqrt{n}}$ to $2^{n^{o(1)}}$. This achievement not only advances Ramsey theory but also provides powerful new tools for handling "weak" randomness.

The Problem: Ramsey Theory and Randomness

The paper tackles two deeply related problems:

  1. Ramsey Theory: A $K$-Ramsey graph is a graph with no clique or independent set of size $K$. The goal is to construct these explicitly for as small a $K$ as possible relative to the number of vertices.
  2. Randomness Extraction: In computer science, we often need "pure" random bits, but physical sources of randomness are often "weak" or biased. A 2-source disperser is an algorithm that takes two independent, weak sources of randomness and produces an output that is guaranteed not to be constant.

A 2-source disperser is mathematically equivalent to the adjacency matrix of a bipartite Ramsey graph. Thus, a breakthrough in disperser construction directly translates to a breakthrough in Ramsey theory. The gap addressed here is the "$\sqrt{n}$ barrier," where previous techniques broke down when the entropy $k$ was less than the square root of the total bits $n$.

Methodology: The Challenge-Response Mechanism

The core innovation is an explicit 2-source disperser for sources with min-entropy $k = 2^{\log^\delta n}$ (where $\delta < 1$). To achieve this, the authors moved beyond existing techniques that failed at low entropy levels.

The paper's table of contents highlights the complex, multi-stage construction of the disperser.

Key technical innovations include:

  • The Challenge-Response Mechanism: This is the "secret sauce." Imagine one source "challenging" the other to find where its entropy is hidden. The authors improved a mechanism from previous work to make it much more sensitive, allowing it to locate entropy concentrations even in very "thin" sources.
  • Recursive Partitioning: To beat the $\sqrt{n}$ barrier, the authors use a "win-win" recursive strategy. They partition the source into blocks. If a block has high entropy, they condense it; if it has low entropy, they use the challenge-response mechanism to identify and fix it, eventually reducing the problem to a state they can solve with existing extractors.
  • Exponential Error Reduction: The authors improved an existing extractor (Rao's) to achieve exponentially small error ($2^{-k^{\Omega(1)}}$) rather than just polynomially small error. This was a crucial prerequisite for their recursive construction to work without the errors blowing up.

Key Results

  • Ramsey Graph Breakthrough: The authors construct a Ramsey graph on $2^n$ vertices that is $K$-Ramsey for $K = 2^{n^{o(1)}}$. This is a massive improvement over the previous $2^{\sqrt{n}}$ limit.
  • Explicit Bipartite Ramsey Graphs: They provide an explicit $N \times N$ Boolean matrix where no $K \times K$ sub-matrix is monochromatic, for $K$ as small as $2^{2^{\log^{1-\alpha} n}}$.
  • New Extractor: They present a new independent sources extractor that can extract from a constant number of sources with polynomially small min-entropy with exponentially small error.

Limitations and Future Work

While the construction is "explicit" (meaning it runs in polynomial time), it is incredibly complex and involves many layers of recursion. It is not a "simple" construction like the Frankl-Wilson one.

Furthermore, the holy grail in this field is to reach $k = \text{poly}(\log n)$ entropy, or even $k = O(\log n)$, which would match the existential bounds proven by Erdős. While this paper makes a huge leap, there is still a gap between $2^{\log^\delta n}$ and $\text{poly}(\log n)$. Finally, the main result for two sources is a disperser (which guarantees the output isn't constant). Creating a full extractor (which guarantees the output is nearly uniform) for two sources at this low entropy level remains an open challenge.

Summary updated

Abstract

The main result of this paper is an explicit disperser for two independent sources on n bits, each of min-entropy k = 2 log n , where < 1 is some absolute constant. Put differently, setting N = 2 n and K = 2 k , we construct an explicit N N Boolean matrix for which no K K sub-matrix is monochromatic. Viewed as the adjacency matrix of a bipartite graph, this gives an explicit construction of a bipartite K-Ramsey graph of 2N vertices. This improves the previous bound of k = o(n) of Barak, Kindler, Shaltiel, Sudakov and Wigderson. As a corollary, we get a construction of a 2 n o(1) (nonbipartite) Ramsey graph of 2 n vertices, significantly improving the previous bound of 2 ( n) due to Frankl and Wilson.
BibTeX
@article{barak2012source,
  author = {Boaz Barak and Anup Rao and Ronen Shaltiel and Avi Wigderson},
  title = {{2-source dispersers for n^o(1) entropy, and Ramsey graphs beating the Frankl-Wilson construction}},
  journal = {Annals},
  year = {2012},
  doi = {10.4007/annals.2012.176.3.3},
}
Figure