Search

Abstract.  In this paper we construct explicit deterministic extractors from polynomial sources, which are distributions sampled by low degree multivariate polynomials over finite fields. This naturally generalizes previous work on extraction from affine sources (which are degree 1 polynomials). A direct consequence is a deterministic extractor for distributions sampled by polynomial size arithmetic circuits over exponentially large fields. The steps in our extractor construction, and the tools (mainly from algebraic geometry) that we use for them, are of independent interest: The first step is a construction of rank extractors, which are polynomial mappings which ‘extract’ the algebraic rank from any system of low degree polynomials. More precisely, for any n polynomials, k of which are algebraically independent, a rank extractor outputs k algebraically independent polynomials of slightly higher degree. The rank extractors we construct are applicable not only over finite fields but also over fields of characteristic zero. The next step is relating algebraic independence to min-entropy. We use a theorem of Wooley to show that these parameters are tightly connected. This allows replacing the algebraic assumption on the source (above) by the natural information theoretic one. It also shows that a rank extractor is already a high quality condenser for polynomial sources over polynomially large fields. Finally, to turn the condensers into extractors, we employ a theorem of Bombieri, giving a character sum estimate for polynomials defined over curves. It allows extracting all the randomness (up to a multiplicative constant) from polynomial sources over exponentially large prime fields. [ABSTRACT FROM AUTHOR]

Abstract.  Mergers are procedures that, with the aid of a short random string, transform k (possibly dependent) random sources into a single random source, in a way that ensures that if one of the input sources has min-entropy rate δ then the output has min-entropy rate close to δ. Mergers were first introduced by Ta-Shma [28th STOC, pp. 276-285, 1996] and have proven to be a very useful tool in explicit constructions of extractors and condensers. In this work we present a new analysis of the merger construction of Lu et al [35th STOC, pp. 602-611, 2003]. We prove that the merger’s output is close to a distribution with min-entropy rate of at least $$\frac{6}{11}\delta$$ . We show that the distance from this distribution is polynomially related to the number of additional random bits that were used by the merger (i.e., its seed). We are also able to prove a bound of $$\frac{4}{7}\delta$$ on the min-entropy rate at the cost of increasing the statistical error. Both results are improvements to the previous known lower bound of $$\frac{1}{2}\delta$$ (however, in the $$\frac{1}{2}\delta$$ result the error decreases exponentially in the length of the seed). To obtain our results we deviate from the usual linear algebra methods that were used by Lu et al and introduce techniques from additive number theory. [ABSTRACT FROM AUTHOR]