Extractors and rank extractors for polynomial sources

Zeev Dvir, Ariel Gabizon, Avi Wigderson

Research output: Chapter in Book/Report/Conference proceedingConference contribution

9 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2007
Pages52-62
Number of pages11
DOIs
StatePublished - Dec 1 2007
Externally publishedYes
Event48th Annual Symposium on Foundations of Computer Science, FOCS 2007 - Providence, RI, United States
Duration: Oct 20 2007Oct 23 2007

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
ISSN (Print)0272-5428

Other

Other48th Annual Symposium on Foundations of Computer Science, FOCS 2007
CountryUnited States
CityProvidence, RI
Period10/20/0710/23/07

All Science Journal Classification (ASJC) codes

  • Engineering(all)

Fingerprint Dive into the research topics of 'Extractors and rank extractors for polynomial sources'. Together they form a unique fingerprint.

Cite this