Skip to main content

Extractors for varieties

Author(s): Dvir, Zeev

To refer to this page use:
Full metadata record
DC FieldValueLanguage
dc.contributor.authorDvir, Zeev-
dc.identifier.citationDvir, Zeev. "Extractors for varieties." Computational Complexity 21, no. 4 (2012): pp. 515-572. doi:10.1007/s00037-011-0023-3.en_US
dc.description.abstractWe study the task of randomness extraction from sources that 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 that 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.en_US
dc.format.extent515 - 572en_US
dc.relation.ispartofComputational Complexityen_US
dc.rightsAuthor's manuscripten_US
dc.titleExtractors for varietiesen_US
dc.typeJournal Articleen_US

Files in This Item:
File Description SizeFormat 
ExtractorsForVarieties.pdf332.45 kBAdobe PDFView/Download

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.