Revision #1 Authors: Kuan Cheng, Ruiyang Wu

Accepted on: 12th July 2024 10:11

Downloads: 77

Keywords:

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.

TR24-040 Authors: Kuan Cheng, Ruiyang Wu

Publication: 29th February 2024 17:15

Downloads: 374

Keywords:

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].