TY - GEN

T1 - Extractors and rank extractors for polynomial sources

AU - Dvir, Zeev

AU - Gabizon, Ariel

AU - Wigderson, Avi

PY - 2007/12/1

Y1 - 2007/12/1

N2 - In this paper 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. A direct consequence is a deterministic extractor for distributions sampled by polynomial size arithmetic circuits over exponentially large fields. The first step towards extraction is a construction of rank extractors, which are polynomial mappings that "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. A result of Wooley allows us to relate algebraic rank and min-entropy and to show that a rank extractor is also a high quality condenser for polynomial sources overpolynomially large fields. Finally, to turn this condenser into an extractor, 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 fields. " 2007 IEEE.

AB - In this paper 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. A direct consequence is a deterministic extractor for distributions sampled by polynomial size arithmetic circuits over exponentially large fields. The first step towards extraction is a construction of rank extractors, which are polynomial mappings that "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. A result of Wooley allows us to relate algebraic rank and min-entropy and to show that a rank extractor is also a high quality condenser for polynomial sources overpolynomially large fields. Finally, to turn this condenser into an extractor, 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 fields. " 2007 IEEE.

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

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

U2 - 10.1109/FOCS.2007.4389479

DO - 10.1109/FOCS.2007.4389479

M3 - Conference contribution

AN - SCOPUS:46749128578

SN - 0769530109

SN - 9780769530109

T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

SP - 52

EP - 62

BT - Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2007

T2 - 48th Annual Symposium on Foundations of Computer Science, FOCS 2007

Y2 - 20 October 2007 through 23 October 2007

ER -