On the Distribution of the Number of Roots of Polynomials and Explicit Logspace Extractors
Tzvika Hartman, Ran Raz · 2000
Weak designs were defined in [10] and are used in constructions of extractors. Roughly speaking, a weak design is a collection of subsets satisfying some near-disjointness properties. Constructions of weak designs with certain parameters are given in [10]. These constructions are explicit in the sense that they require time and space polynomial in the number of subsets. However, the constructions require time and space polynomial in the number of subsets even when needed to output only one specific subset out of the collection. Hence, the constructions are not explicit in a stronger sense. In this work we provide constructions of weak designs (with parameters similar to the ones of [10]) that can be carried out in space logarithmic in the number of subsets. Moreover, our constructions are explicit even in a stronger sense; given an index to a subset, we output the specified subset in time and space polynomial in the size of the index. Using our constructions, we obtain ext...