Explicit Two-Source Extractors and Resilient Functions

Oded's comments

This is a fantastic result!

It would have been great to see any explicit two-source extractor for min-entropy rate below one half, let alone one that beats Bourgain's rate of 0.499. Handling any constant min-entropy rate would have been a feast (see A Challenge from the mid-1980s), and going beyond that would have justified a night-long party. A next challenge could have been handling min-entropy $n^c$, for any constant $c>0$. But the current work ``saves'' us all these intermediate celebrations by presenting us with a construction that handles poly-logarithmic min-entropy.

Yes, one can be greedy and seek to extract more bits and/or obtain a negligible extraction error. But let's party today...

Overview (following presentation of Gil Cohen, Aug 2015)

The main theorem is proved by combining two (non-standard types of) extractors.

1. A (seeded) non-maleable extractor, denoted nmEXT, that handles independence parameter $t$ and min-entropy $k=\poly(t\log n)$ using a seed of length $d'=\poly(t\log n)$, given by [CGL15].
   Loosely speaking, such an extractor produces $2^{d'}$ outputs such that for every admissible source $X$ almost all outputs are almost $t$-wise independent.
2. A (seedless) extractor for "quasi non-oblivious bit fixing sources" in which the number of bad locations is at most $n^{0.99}$ and the good locations are distributed in an almost polylog-wise independent manner. (It may be that the constant in the exponent is not 0.99, but any constant greater than 0.5 will do.)
   This extractor is constructed by first presenting an explicit construction for the non-oblivious bit-fixing model with parameters as above, and that satisfies the following additional requirement (0) the function is balanced, (1) it is monotone, and (2) it is computable in AC0.
   To see the role of these extra requirements, consider a circuit $C$ that satisfies them all. Then, by monotonicity of $C$, the output of $C$ is influenced by a coalision $B$ of size $b$, given an assignment $r$ to $[n]-B$, if and only if $C_{B=0^b}(r) \neq C_{B=1^b}(r)$. We know that the probability of the latter event is small when $b=n^{0.99}$ and $r$ is uniformly distributed. Since $C$ is in AC0, it follows that the same holds when $r$ is polylog-wise independent (by Braverman). Likewise, since $C$ is balanced (and using Braverman again), the output is almost unbiased.

Denoting the latter extractor (for non-oblivious bit-fixing sources) by bfEXT, and using an ordinary extractor EXT that uses a seed of length $d=O(log n)$ and extracts $d'$ bits, we obtain the two-source extractor that, on input $(x,y)\in(\{0,1\}^n)^2$, proceeds as follows:
1. For every $d$-bit long seed $s$, produces $z_s=nmEXT(y,E(x,s))$;
2. letting $z = z_{0^d}\cdots z_{1^d}$, it outputs bfEXT(z).
N.B.: Using a polylog independence parameter for nmEXT, requires having a seed of super-logarithmic seed. The standrad extractor EXT is used to extract such a seed from the first source X, and this is used to sample seeds of the nmEXT.

The original abstract

We explicitly construct an extractor for two independent sources on $n$ bits, each with min-entropy at least $\log^C n$ for a large enough constant $C$. Our extractor outputs one bit and has error $n^{-\Omega(1)}$. The best previous extractor, by Bourgain [B2], required each source to have min-entropy $.499n$.

A key ingredient in our construction is an explicit construction of a monotone, almost-balanced boolean function on $n$ bits that is resilient to coalitions of size $n^{1-\delta}$, for any $\delta>0$. In fact, our construction is stronger in that it gives an explicit extractor for a generalization of non-oblivious bit-fixing sources on $n$ bits, where some unknown $n-q$ bits are chosen almost $polylog(n)$-wise independently, and the remaining $q=n^{1-\delta}$ bits are chosen by an adversary as an arbitrary function of the $n-q$ bits. The best previous construction, by Viola \cite{Viola14}, achieved $q=n^{1/2 - \delta}$.

Our other main contribution is a reduction showing how such a resilient function gives a two-source extractor. This relies heavily on the new non-malleable extractor of Chattopadhyay, Goyal and Li [CGL15].

Our explicit two-source extractor directly implies an explicit construction of a $2^{(\log \log N)^{O(1)}}$-Ramsey graph over $N$ vertices, improving bounds obtained by Barak et al. [BRSW12] and matching independent work by Cohen [Coh15b].

See ECCC TR15-119.