期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2020
卷号：2020
页码：1-19
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：An (n, r, s)-design, or (n, r, s)-partial Steiner system, is an r-uniform hypergraph over n vertices with pairwise hyperedge intersections of size 0, we extract from (N, K, n, k)-adversarial sources of locality 0, where K ≥ Nδ and k ≥ polylog n. The previous best result (Chattopadhyay et al., STOC 2020) required K ≥ N1/2 o(1). As a result, we get extractors for small-space sources over n bits with entropy requirement k ≥ n 1/2 δ , whereas the previous best result (Chattopadhyay et al., STOC 2020) required k ≥ n 2/3 δ .
