Extractors for Varieties

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

11 Scopus citations

Abstract

We study the task of randomness extraction from sources which are distributed uniformly on an unknown algebraic variety. In other words, we are interested in constructing a function (an extractor) whose output is close to uniform even if the input is drawn uniformly from the set of solutions of an unknown system of low degree polynomials. This problem generalizes the problem of extraction from affine sources which has drawn a considerable amount of interest lately. We present two constructions of explicit extractors for varieties. The first works for varieties of any size (including one dimensional varieties, or curves) and requires field size which is exponential in the overall dimension of the space. Our second extractor allows the field size to be polynomial in the degree of the equations defining the variety, but works only for varieties whose size is at least the square root of the total size of the space.

Original languageEnglish (US)
Title of host publicationProceedings of the 2009 24th Annual IEEE Conference on Computational Complexity, CCC 2009
Pages102-113
Number of pages12
DOIs
StatePublished - Nov 9 2009
Externally publishedYes
Event2009 24th Annual IEEE Conference on Computational Complexity, CCC 2009 - Paris, France
Duration: Jul 15 2009Jul 18 2009

Publication series

NameProceedings of the Annual IEEE Conference on Computational Complexity
ISSN (Print)1093-0159

Other

Other2009 24th Annual IEEE Conference on Computational Complexity, CCC 2009
CountryFrance
CityParis
Period7/15/097/18/09

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Computational Mathematics

Fingerprint Dive into the research topics of 'Extractors for Varieties'. Together they form a unique fingerprint.

  • Cite this

    Dvir, Z. (2009). Extractors for Varieties. In Proceedings of the 2009 24th Annual IEEE Conference on Computational Complexity, CCC 2009 (pp. 102-113). [5231245] (Proceedings of the Annual IEEE Conference on Computational Complexity). https://doi.org/10.1109/CCC.2009.7