2026-08-18T03:43:48Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:21062 2024-09-16T06:02:39Z ddc:004 open_access

Randomness Extractors in AC⁰ and NC¹: Optimal up to Constant Factors Cheng, Kuan Wu, Ruiyang randomness extractor uniform AC⁰ error reduction uniform NC¹ disperser We study randomness extractors in AC⁰ and NC¹. For the AC⁰ setting, we give a logspace-uniform construction such that for every k ≥ n/poly log n, ε ≥ 2^{-poly log n}, it can extract from an arbitrary (n, k) source, with a small constant fraction entropy loss, and the seed length is O(log n/(ε)). The seed length and output length are optimal up to constant factors matching the parameters of the best polynomial time construction such as [Guruswami et al., 2009]. The range of k and ε almost meets the lower bound in [Goldreich et al., 2015] and [Cheng and Li, 2018]. We also generalize the main lower bound of [Goldreich et al., 2015] for extractors in AC⁰, showing that when k < n/poly log n, even strong dispersers do not exist in non-uniform AC⁰. For the NC¹ setting, we also give a logspace-uniform extractor construction with seed length O(log n/(ε)) and a small constant fraction entropy loss in the output. It works for every k ≥ O(log² n), ε ≥ 2^{-O(√k)}. Our main techniques include a new error reduction process and a new output stretch process, based on low-depth circuit implementations for mergers, condensers, and somewhere extractors. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Kuan Cheng and Ruiyang Wu 2024 Is Part Of LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2024.69 urn:nbn:de:0030-drops-210623 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.69 eng https://creativecommons.org/licenses/by/4.0/legalcode