TY - JOUR

T1 - Extractors and rank extractors for polynomial sources

AU - Dvir, Zeev

AU - Gabizon, Ariel

AU - Wigderson, Avi

N1 - Funding Information:
We would like to thank Ran Raz and Amir Shpilka for numerous helpful conversations. We thank Jean Bourgain for bringing to our attention the results of Wooley (1996) and Bombieri(1966). We are grateful to Salil Vadhan for his ideapresentedinSection6. WethankAndrejBogdanovandGilAlonforhelp-ful conversations. The first two authors were supported by Binational Science Foundation (BSF) grant and by Minerva Foundation grant.

PY - 2009/4

Y1 - 2009/4

N2 - 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.

AB - 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.

KW - Derandomization

KW - Extractors

UR - http://www.scopus.com/inward/record.url?scp=67349179079&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=67349179079&partnerID=8YFLogxK

U2 - 10.1007/s00037-009-0258-4

DO - 10.1007/s00037-009-0258-4

M3 - Article

AN - SCOPUS:67349179079

SN - 1016-3328

VL - 18

SP - 1

EP - 58

JO - Computational Complexity

JF - Computational Complexity

IS - 1

ER -