Affine dispersers from subspace polynomials
Affine dispersers from subspace polynomials
复制标题
DOI：
10.1145/1536414.1536426
复制
发表时间：
2009-05
期刊：
影响因子：
--
通讯作者：
Eli Ben-Sasson;Swastik Kopparty
中科院分区：
文献类型：
--
作者：
Eli Ben-Sasson;Swastik Kopparty
对于维数为d的源，F2n上的仿射分散器是一个函数f: F2n→F2，使得对于任何至少维数为d的仿射空间S≤F2n，在S} = F2中有{f(S): S。在从不完全随机性的结构化来源中确定性地提取随机性的背景下，已经考虑了仿射分散体。以前，由于Barak等人[2]和Bourgain[10]（后者实际上给出了更强的对象，称为仿射提取器），已知每个d = Ω(n)的仿射分散器的显式结构。本文首次给出了次线性维的显式仿射色散。具体来说，我们的分散器即使在d = Ω（n4/5）时也能工作。我们的构造的主要新颖之处在于证明方法，它依赖于子空间多项式的初等性质。相比之下，前面提到的工作依赖于有限域的和积定理。
An affine disperser over F2n for sources of dimension d is a function f: F2n → F2 such that for any affine space S ⊆ F2n of dimension at least d, we have {f(s) : s in S} = F2. Affine dispersers have been considered in the context of deterministic extraction of randomness from structured sources of imperfect randomness. Previously, explicit constructions of affine dispersers were known for every d = Ω(n), due to Barak et. al.[2] and Bourgain[10] (the latter in fact gives stronger objects called affine extractors). In this work we give the first explicit affine dispersers for sublinear dimension. Specifically, our dispersers work even when d = Ω(n4/5). The main novelty in our construction lies in the method of proof, which relies on elementary properties of subspace polynomials. In contrast, the previous works mentioned above relied on sum-product theorems for finite fields.