Extractors for Polynomial Sources over Fields of Constant Order and Small Characteristic

By Eli Ben-Sasson, Ariel Gabizon. 2013

12 citations recorded by the source corpus.

A polynomial source of randomness over F n is a random variable X = f(Z) where f is a polynomial map and Z is a random variable distributed uniformly over F r for some integer r. The three main parameters of interest associated with a polynomial source are the order q of the field, the (total) degree D of the map f , and the base-q logarithm of the size of the range of f over inputs in F r , denoted by k. For simplicity we call X a (q; D; k)-source.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Geometry and Topology