We study randomness extractors in $\AC^0$ and $\NC^1$.
We give a logspace-uniform construction of $\AC^0$ computable extractors such that for every $k \ge n/\poly \log n, \varepsilon \ge 2^{-\poly \log n}$, it can extract from any $(n, k)$ source, with its output $\varepsilon$-close to uniform, with only a small constant fraction entropy loss, and the seed length is $O(\log ({n}/{\varepsilon}))$.
The seed length and output length are optimal up to constant factors matching the parameters of the best polynomial time construction, such as that by Guruswami et al.\ (JACM'09).
The range of $k$ and $\varepsilon$ almost meets the lower bound for $\AC^0$ extractors established by Goldreich et al.\ (CCC'15) and Cheng and Li (APPROX/RANDOM'18).
We also generalize the lower bound by Goldreich et al.\
for extractors in $\AC^0$, showing that when $k < n/ \poly \log n$, even strong dispersers do not exist in non-uniform $\AC^0$.
We also give a logspace-uniform construction of $\NC^1$ computable extractors with seed length $O(\log ({n}/{\varepsilon}))$ and with a small constant fraction entropy loss in the output. It can extract from any $(n, k)$ source to attain $\varepsilon$-close to uniform output distributions, for every $k \ge \Omega(\log (n/\varepsilon)), \varepsilon\ge 2^{-k^{0.99}}$.
Our $\AC^0$ extractors and $\NC^1$ extractors can be computed in $O(1)$ and $O(\log n)$ time by certain parallel random-access machine models respectively.

Our main techniques include a new error reduction process and a new output stretch process, which are based on low-depth circuits implementations for mergers, condensers, and somewhere extractors.

We improved the construction for $\mathrm{NC}^1$ extractors, which now work for every $k \ge \Omega(\log (n/\varepsilon)), \varepsilon\ge 2^{-k^{0.99}}$. We also added discussion about implementing extractors in parallel computation models.

We study extractors computable in uniform $\mathrm{AC}^0$ and uniform $\mathrm{NC}^1$.

For the $\mathrm{AC}^0$ setting, we give a construction such that for every $k \ge n/ \mathrm{poly} \log n, \eps \ge 2^{-\mathrm{poly} \log n}$, it can extract $(1-\gamma)k$ randomness from an $(n, k)$ source for an arbitrary constant $\gamma$, with seed length $O(\log \frac{n}{\epsilon})$. The output length and seed length are optimal up to constant factors matching the parameters of the best polynomial time construction such as [GUV09]. The range of $k$ and $\epsilon$ almost meets the lower bound in [GVW15] and [CL18].We also generalize the main lower bound of [GVW15] for extractors in $\mathrm{AC}^0$, showing that when $k < n/ \mathrm{poly} \log n$, even strong dispersers do not exist in $\mathrm{AC}^0$.

For the $\mathrm{NC}^1$ setting, we also give a construction with seed length $O(\log \frac{n}{\epsilon})$ and a small constant fraction entropy loss in the output. The construction works for every $k \ge O(\log^2 n), \epsilon\ge 2^{-O(\sqrt{k})}$. To our knowledge the previous best $\mathrm{NC}^1$ construction is Trevisan's extractor [Tre01] and its improved version[RRV02] which have seed lengths $\mathrm{poly} \log \frac{n}{\epsilon}$.

Our main techniques include a new error reduction process and a new output stretch process based on low depth circuits implementations for mergers from [DKSS13], condensers from [KT22] and somewhere extractors from [Ta-98].

We revised the proofs and fixed some problems in this paper.

We study extractors computable in uniform $\mathrm{AC}^0$ and uniform $\mathrm{NC}^1$.

For the $\mathrm{AC}^0$ setting, we give a construction such that for every $k \ge n/ \mathrm{poly} \log n, \eps \ge 2^{-\mathrm{poly} \log n}$, it can extract $(1-\gamma)k$ randomness from an $(n, k)$ source for an arbitrary constant $\gamma$, with seed length $O(\log \frac{n}{\epsilon})$. The output length and seed length are optimal up to constant factors matching the parameters of the best polynomial time construction such as [GUV09]. The range of $k$ and $\epsilon$ almost meets the lower bound in [GVW15] and [CL18].We also generalize the main lower bound of [GVW15] for extractors in $\mathrm{AC}^0$, showing that when $k < n/ \mathrm{poly} \log n$, even strong dispersers do not exist in $\mathrm{AC}^0$.

For the $\mathrm{NC}^1$ setting, we also give a construction with seed length $O(\log \frac{n}{\epsilon})$ and a small constant fraction entropy loss in the output. The construction works for every $k \ge O(\log^2 n), \epsilon\ge 2^{-O(\sqrt{k})}$. To our knowledge the previous best $\mathrm{NC}^1$ construction is Trevisan's extractor [Tre01] and its improved version[RRV02] which have seed lengths $\mathrm{poly} \log \frac{n}{\epsilon}$.

Our main techniques include a new error reduction process and a new output stretch process based on low depth circuits implementations for mergers from [DKSS13], condensers from [KT22] and somewhere extractors from [Ta-98].