论文标题
品种图像的提取器
Extractors for Images of Varieties
论文作者
论文摘要
我们为品种的多项式图像构造了明确的确定性提取器，即通过将低度多项式图$ f应用于$ f：\ mathbb {f} _q^r \ to \ m mathbb {f} _q^n $从A $ k $ k $ k $ -dimeNsional采样的元素随机采样，从而将分布进行采样。 \ Mathbb {f} _Q^r $。这类来源概括了由DVIR，Gabizon和Wigderson研究的多项式来源（FOCS 2007，Comput。Complex。2009），以及由DVIR研究的多种源（CCC 2009，Comput。Complex.2012）。 假设地图$ f $和多样性$ v $上的某些天然非定位条件，特别是确保源具有足够的最小内向拷贝，我们几乎提取了分布的所有最小渗透率。与DVIR-GABIZON-WIGDERSON和DVIR结果不同，我们的构造在足够大的任意特征有限的领域中起作用。我们建筑的一个关键部分是改进的品种确定性排名提取器。作为副产品，我们获得了仿射品种和仿射代数的显式Noether归一化引理。 此外，我们通过将其扩展到全甲分析量大小的所有有限的素数，从而概括了由于Bourgain，DVIR和Leeman（Comput。Complex。2016）而引起的拟指数误差的仿期提取器的构造。
We construct explicit deterministic extractors for polynomial images of varieties, that is, distributions sampled by applying a low-degree polynomial map $f : \mathbb{F}_q^r \to \mathbb{F}_q^n$ to an element sampled uniformly at random from a $k$-dimensional variety $V \subseteq \mathbb{F}_q^r$. This class of sources generalizes both polynomial sources, studied by Dvir, Gabizon and Wigderson (FOCS 2007, Comput. Complex. 2009), and variety sources, studied by Dvir (CCC 2009, Comput. Complex. 2012). Assuming certain natural non-degeneracy conditions on the map $f$ and the variety $V$, which in particular ensure that the source has enough min-entropy, we extract almost all the min-entropy of the distribution. Unlike the Dvir-Gabizon-Wigderson and Dvir results, our construction works over large enough finite fields of arbitrary characteristic. One key part of our construction is an improved deterministic rank extractor for varieties. As a by-product, we obtain explicit Noether normalization lemmas for affine varieties and affine algebras. Additionally, we generalize a construction of affine extractors with exponentially small error due to Bourgain, Dvir and Leeman (Comput. Complex. 2016) by extending it to all finite prime fields of quasipolynomial size.
