TY - GEN

T1 - Extractors for Varieties

AU - Dvir, Zeev

PY - 2009/11/9

Y1 - 2009/11/9

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

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

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

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

U2 - 10.1109/CCC.2009.7

DO - 10.1109/CCC.2009.7

M3 - Conference contribution

AN - SCOPUS:70350641078

SN - 9780769537177

T3 - Proceedings of the Annual IEEE Conference on Computational Complexity

SP - 102

EP - 113

BT - Proceedings of the 2009 24th Annual IEEE Conference on Computational Complexity, CCC 2009

T2 - 2009 24th Annual IEEE Conference on Computational Complexity, CCC 2009

Y2 - 15 July 2009 through 18 July 2009

ER -