Two Source Extractors for Asymptotically Optimal Entropy, and (Many) More

Oded's comments

I have posted numerous recommendations for this line of work (e.g., in July 2009, Feb 2013, 9-March 2015, 23-March 2015, June 2015, July 2015, Aug 2015, Nov 2015, and July 2016), but at some point I stopped reporting of the continued flow of improvements.

Actually, I should stress upfront that my own focus here is on the construction of two-source extractors, which I consider the most important objective per se. In that respect there are three key parameters:

1. The min-entropy bound, denoted $k=k(n)$ (imposed on the $n$-bit sources).
2. The output length, denoted $m=m(n)$.
3. The error (or deviation) bound, denoted $\eps$.
   Actually, the min-entropy bound depends on $\eps$, so one better denote the former by $k(n,\eps)$.

The current paper obtains the optimal min-entropy bound, up to a constant factor; that is it achieves $k=O(\log n)$, improving over the prior bound of $k=\tildeO(\log n)$. One can be gready and seek $k=O(1)+\log_2 n$, but I think it is far more important to obtained any desired error level $\eps$, while aiming at $k=\poly(\log(n/\eps))$ (or even $k=O(\log(n/\eps))$ if one is greeady) and $m=\Omega(k)$ (or ``only'' $m=k^{\Omega(1)}$).

I am not sure I recommend reading the paper, which seems to target the experts in the area only. I only read parts of the introduction, and (as can be guessed from the foregoing) I would have written it very differently.

The original abstract

A long line of work in the past two decades or so established close connections between several different pseudorandom objects and applications, including seeded or seedless non-malleable extractors, two source extractors, (bipartite) Ramsey graphs, privacy amplification protocols with an active adversary, non-malleable codes and many more. These connections essentially show that an asymptotically optimal construction of one central object will lead to asymptotically optimal solutions to all the others. However, despite considerable effort, previous works can get close but still lack one final step to achieve truly asymptotically optimal constructions.

In this paper we provide the last missing link, thus simultaneously achieving explicit, asymptotically optimal constructions and solutions for various well studied extractors and applications, that have been the subjects of long lines of research. Our results include:

1. Asymptotically optimal seeded non-malleable extractors, which in turn give two source extractors for asymptotically optimal min-entropy of $O(\log n)$, explicit constructions of $K$-Ramsey graphs on $N$ vertices with $K=\log^{O(1)} N$, and truly optimal privacy amplification protocols with an active adversary.
2. Two source non-malleable extractors and affine non-malleable extractors for some linear min-entropy with exponentially small error, which in turn give the first explicit construction of non-malleable codes against $2$-split state tampering and affine tampering with constant rate and \emph{exponentially} small error.
3. Explicit extractors for affine sources, sumset sources, interleaved sources, and small space sources that achieve asymptotically optimal min-entropy of $O(\log n)$ or $2s+O(\log n)$ (for space $s$ sources).
4. An explicit function that requires strongly linear read once branching programs of size $2^{n-O(\log n)}$, which is optimal up to the constant in $O(\cdot)$. Previously, even for standard read once branching programs, the best known size lower bound for an explicit function is $2^{n-O(\log^2 n)}$.

See ECCC TR23-023.