Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR24-040 | 29th February 2024 06:42

Randomness Extractors in $\mathrm{AC}^0$ and $\mathrm{NC}^1$: Optimal up to Constant Factors


Authors: Kuan Cheng, Ruiyang Wu
Publication: 29th February 2024 17:15
Downloads: 153


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

ISSN 1433-8092 | Imprint