Computer Science/Discrete Mathematics Seminar I

In this work we construct explicit deterministic extractors from polynomial sources, namely from 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 first step of our construction, which seems to be of independent interest, 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. We observe (using a theorem of Wooley) that a tight connection exists between the algebraic rank of a polynomial source and its min-entropy. This connection shows that our rank extractor is already a high quality condenser for polynomial sources over polynomially larger fields. The second step in our construction uses tools from algebraic geometry, most notably a theorem of Bombieri giving a character sum estimate for polynomials defined over curves. Using the rank extractor constructed in the first step, we can transform, deterministically, any polynomial source into a source sampled by algebraically independent polynomials (a full rank source). Using Bombieri's theorem, we succeed in extracting all the randomness (up to a multiplicative constant) from such full rank sources. Combining these two steps gives a deterministic extractor for polynomial sources of any rank over exponentially large fields. (Joint work with Ariel Gabizon and Avi Wigderson)