Explicit Designs and Extractors
share
We give significantly improved explicit constructions of three related pseudorandom objects. 1. Extremal designs: 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 <s. For all constants r≥ s∈ℕ with r even, we explicitly construct (n,r,s)-designs (G_n)_n∈ℕ with independence number α(G_n)≤ O(n^2(r-s)/r). This gives the first derandomization of a result by Rödl and Šinajová (Random Structures Algorithms, 1994). 2. Extractors for adversarial sources: By combining our designs with leakage-resilient extractors (Chattopadhyay et al., FOCS 2020), we establish a new, simple framework for extracting from adversarial sources of locality 0. As a result, we obtain significantly improved low-error extractors for these sources. For any constant δ>0, we extract from (N,K,n, polylog(n))-adversarial sources of locality 0, given just K≥ N^δ good sources. The previous best result (Chattopadhyay et al., STOC 2020) required K≥ N^1/2+o(1). 3. Extractors for small-space sources: Using a known reduction to adversarial sources, we immediately obtain improved low-error extractors for space s sources over n bits that require entropy k≥ n^1/2+δ· s^1/2-δ, whereas the previous best result (Chattopadhyay et al., STOC 2020) required k≥ n^2/3+δ· s^1/3-δ. On the other hand, using a new reduction from small-space sources to affine sources, we obtain near-optimal extractors for small-space sources in the polynomial error regime. Our extractors require just k≥ s·log^Cn entropy for some constant C, which is an exponential improvement over the previous best result, which required k≥ s^1.1·2^log^0.51n (Chattopadhyay and Li, STOC 2016).
READ FULL TEXT