• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Approximation, randomization, and combinatorial optimization : Algorithms and techniques >Extractors for Polynomials Sources over Constant-Size Fields of Small Characteristic
【24h】

Extractors for Polynomials Sources over Constant-Size Fields of Small Characteristic

机译：小特征的恒定大小字段上的多项式源提取器

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

A polynomial source of randomness over F_q~n is a random variable X = f(Z) where f is a polynomial map and Z is a random variable distributed uniformly on F_q~r for some integer r. The three main parameters of interest associated with a polynomial source are the field size q, the (total) degree D of the map f, and the "rate" k which specifies how many different values does the random variable X take, where rate k means X is supported on at least q~k different values. For simplicity we call X a (q, D, k)-source. Informally, an extractor for (q, D, k)-sources is a deterministic function E : F_q~n → {0, l}~m such that the distribution of the random variable E(X) is close to uniform on {0, 1}~m for any (q, D, k)-source X. Generally speaking, the problem of constructing deterministic extractors for such sources becomes harder as q and k decrease and as D grows larger. The only previous work of [Dvir et al., FOCS 2007] construct extractors for such sources when q n. In particular, even for D = 2 no constructions were known for any fixed finite field. In this work we construct for the first time extractors for (q, D, k)-sources for constant-size fields. Our proof builds on the work of DeVos and Gabizon [CCC 2010] on extractors for affine sources, with two notable additions (described below). Like [DG10], our result makes crucial use of a theorem of Hou, Leung and Xiang [J. Number Theory 2002] giving a lower bound on the dimension of products of subspaces. The key insights that enable us to extend these results to the case of polynomial sources of degree D greater than 1 are 1. A source with support size q~k must have a linear span of dimension at least k, and in the setting of low-degree polynomial sources it suffices to increase the dimension of this lineax span. 2. Distinct Frobenius automorphisms of a (single) low-degree polynomial source are 'pseudo-independent' in the following sense: Taking the product of distinct automorphisms (of the very same source) increases the dimension of the linear span of the source.
机译：F_q_n上的多项式随机源是随机变量X = f（Z），其中f是多项式图，Z是在F_q_r上均匀分布于某个整数r的随机变量。与多项式源相关的三个重要的主要参数是字段大小q，映射f的（总）度D和“比率” k，它指定随机变量X取多少个不同的值，其中比率k意味着X在至少q〜k个不同的值上受支持。为简单起见，我们将X称为（q，D，k）源。非正式地，（q，D，k）源的提取器是确定性函数E：F_q〜n→{0，l}〜m，使得随机变量E（X）的分布在{0上接近均匀，对于任何（q，D，k）源X，1}〜m。一般而言，随着q和k的减小以及D的增大，为这种源构造确定性提取器的问题变得更加困难。当D >> n时，[Dvir等人，FOCS 2007]的先前工作仅是为此类来源构造提取器。特别是，即使对于D = 2，对于任何固定的有限域，也没有已知的构造。在这项工作中，我们首次为恒定大小的字段构造（q，D，k）源的提取器。我们的证明建立在DeVos和Gabizon [CCC 2010]在仿射源提取器上的工作基础上，其中有两个值得注意的补充（如下所述）。像[DG10]一样，我们的结果关键地使用了侯，梁和项的一个定理。数论2002]给出了子空间乘积维数的下限。使我们能够将这些结果扩展到度数大于1的多项式源的关键见解是1。支持大小为q〜k的源必须具有至少为k的线性范围，并且在低的情况下阶多项式源足以增加此线轴跨度的尺寸。 2.在一个意义上，（单个）低次多项式源的截然不同的Frobenius自同构是“伪独立的”：取（相同源的）不同自同构的乘积会增加源的线性跨度。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号