Extractors for Images of Varieties
Extractors for Images of Varieties
复制标题
DOI：
10.1145/3564246.3585109
复制
发表时间：
2022-11
期刊：
影响因子：
--
通讯作者：
Zeyu Guo;Ben lee Volk;Akhil Jalan;David Zuckerman
中科院分区：
文献类型：
--
作者：
Zeyu Guo;Ben lee Volk;Akhil Jalan;David Zuckerman
我们构造显式确定性提取器的多项式图像的品种，即，通过应用低次多项式映射f：Fqr → Fqn的分布采样的元素均匀随机从k维品种V <$Fqr。这类源概括了由Dvir、Gabizon和Wigderson研究的两种多项式源（FOCS 2007，Comput.复杂. 2009），和品种来源，由Dvir研究（CCC 2009，Comput.复杂. 2012年）。假设某些自然的非退化条件的地图f和品种V，特别是确保源有足够的最小熵，我们提取几乎所有的最小熵的分布。与Dvir-Gabizon-Wigderson和Dvir的结果不同，我们的构造适用于任意特征的足够大的有限域。我们的建设的一个关键部分是一个改进的确定性排名提取品种。作为副产品，我们得到明确的Noether正规化引理的仿射簇和仿射代数。此外，我们推广了仿射提取器的构造，由于Bourgain，Dvir和Leeman（Comput.复杂. 2016），将其扩展到所有准多项式大小的有限素域。
We construct explicit deterministic extractors for polynomial images of varieties, that is, distributions sampled by applying a low-degree polynomial map f : Fqr → Fqn to an element sampled uniformly at random from a k-dimensional variety V ⊆ Fqr. 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.