The first part of this work settles a disagreement between Avi and me, in his favor. My own position was based, not on seeing a fundamental reason as to why such extractors are impossible, but rather on seeing how the approaches we had in mind fail. Indeed, as noted at the time buy Avi, this is not a good reason. Yet, what was intriguing me was the failure of various amplification methods, of the type that seemed needed for such extractors.
The new extractor just avoids such strong amplifications, although it does use weaker amplifications (of the strength used in our own paper). The starting point is Luca's original idea that the NW-construction has an extractor analogue and applying this observation to the IW-construction. (That is, I refer to the first presentation in Apdx D.4.2.2 of my complexity book, rather than to the alternative presentation, which follows it and is more known and used.)
Recall that the said construction interprets the $n$-bit long input source $x$ as a Boolean function (over the set of $\ell$-bit long strings, where $\ell=\log n$). Viewing this function as a potentially worst-case hard function, one applies the IW-construction to it, which involves various amplification steps as well as an application of the NW-construction at the end. (In contrast, in the alternative presentation, the input $x$ is encoded via a strong error-correcting code into a polynomially longer string $y$, which is viewed as a strongly inapproximable predicate to which the NW-construction is directly applied.)
The new idea is to use the first route (of IW), but avoid the first amplification step, which amplifies from worst-case to mild average-case and is the only "strong amplification step" in this construction. (N.B.: This is not to suggest that the other steps are easy, but rather that the amplification performed by them is very local and can be implemented in AC0.) In terns of pseudorandom generators, this makes sense only if the original function is mildly hard, which is a weird (in-the-middle) starting point for that context (cf [NW] vs [IW], each taking a different extreme). The key observation is that this starting point is a reasonable one for the context of randomness extractors: A $n$-bit long string selected from a source of entropy $n/\poly(\log n)$ is likely to be moderately hard (wrt programs of description length $n/\poly(\log n))$), and not only worst-case hard.
See ECCC TR16-018.
We study two variants of seeded randomness extractors. The first one, as studied by Goldreich et al. \cite{goldreich2015randomness}, is seeded extractors that can be computed by $AC^0$ circuits. The second one, as introduced by Bogdanov and Guo \cite{bogdanov2013sparse}, is (strong) extractor families that consist of sparse transformations, i.e., functions that have a small number of overall input-output dependencies (called \emph{sparse extractor families}). In this paper we focus on the stronger condition where any function in the family can be computed by local functions. The parameters here are the length of the source $n$, the min-entropy $k=3Dk(n)$, the seed length $d=3Dd(n)$, the output length $m=3D= m(n)$, the error $\epsilon=3D\epsilon(n)$, and the locality of functions $\ell=3D\ell(n)$.
In the $AC^0$ extractor case, our main results substantially improve the positive results in \cite{goldreich2015randomness}, where for $k \geq n/\poly(\log n)$ a seed length of $O(m)$ is required to extract $m$ bits with error $1/\poly(n)$. We give constructions of strong seeded extractors for $k=3D\delta n \geq n/\poly(\log n)$, with seed length $d=3DO(\log n)$, output length $m=3Dk^{\Omega(1)}$, and error any $1/\poly(n)$. We can then boost the output length to $\Omega(\delta k)$ with seed length $d=3DO(\log n)$, or to $(1-\gamma)k$ for any constant $0<\gamma<1$ with $d=3DO(\frac{1}{\delta}\log n)$. In the special case where $\delta$ is a constant and $\epsilon=3D1/\poly(n)$, our parameters are essentially optimal. In addition, we can reduce the error to $2^{-\poly(\log n)}$ at the price of increasing the seed length to $d=3D\poly(\log n)$.
In the case of sparse extractor families, Bogdanov and Guo \cite{bogdanov2013sparse} gave constructions for any min-entropy $k$ with locality at least $O(n/k\log (m/\epsilon)\log (n/m))$, but the family size is quite large, i.e., $2^{nm}$. Equivalently, this means the seed length is at least $nm$. In this paper we significantly reduce the seed length. For $k \geq n/\poly(\log n)$ and error $1/\poly(n)$, our $AC^0$ extractor with output $k^{\Omega(1)}$ also has small locality $\ell=3D\poly(\log n)$, and the seed length is only $O(\log n)$. We then show that for $k \geq n/\poly(\log n)$ and $\epsilon \geq 2^{-k^{\Omega(1)}}$, we can use our error reduction techniques to get a strong seeded extractor with seed length $d =3DO(\log n + \frac{\log^2(1/\epsilon)}{\log n})$, output length = $m =3D k^{\Omega(1)}$ and locality $ \log^2 (1/\epsilon) \poly(\log n) $. Finally, for min-entropy $k=3D\Omega(\log^2 n)$ and error $\epsilon \geq 2^{-k^{\Omega(1)}}$, we give a strong seeded extractor with seed length $d =3D O(k)$, $m =3D (1-\gamma)k$ and locality $\frac{n}{k}\log^2 (1/\epsilon= ) (\log n)\poly(\log k)$. As an intermediate tool for this extractor, we construct a condenser that condenses an $(n, k)$-source into a $(10k, \Omega(k))$-source with seed length $d=3DO(k)$, error $2^{-\Omega(k)}$ and locality $\Theta(\frac{n}{k}\log n)$.
See ECCC TR16-018.