Low-Degree Polynomials Extract from Local Sources
Low-Degree Polynomials Extract from Local Sources
复制标题
DOI：
10.48550/arxiv.2205.13725
复制
发表时间：
2022-05
期刊：
影响因子：
--
通讯作者：
Omar Alrabiah;Eshan Chattopadhyay;J. Goodman;Xin Li;João L. Ribeiro
中科院分区：
文献类型：
--
作者：
Omar Alrabiah;Eshan Chattopadhyay;J. Goodman;Xin Li;João L. Ribeiro
我们继续从简单过程产生的弱源中提取随机位的工作。我们专注于局部采样源的模型，其中源中的每个位取决于少量的（隐藏的）均匀随机输入位。也被称为本地源，这个模型是由De和沃森（TOCT 2012）和Viola（SICOMP 2014）引入的，并且与$\mathsf{AC}^0$电路和有界宽度分支程序生成的源密切相关。特别是，本地源的提取器也适用于这些经典计算模型生成的源。尽管在十年前就被引入，但在提高从本地源提取的熵要求方面几乎没有取得进展。目前最好的显式提取器需要熵$n^{1/2}$，并通过减少仿射提取器。首先，我们证明了一个障碍，表明人们不能希望通过这种形式的黑盒减少来改善这种熵的要求。特别是需要新的技术。在我们的主要结果中，我们试图回答低次多项式（超过$\mathbb{F}_2$）是否有可能打破这个障碍。我们回答这个问题是肯定的，并充分刻画了低次多项式作为本地源提取器的能力。更确切地说，我们表明，一个随机度$r$多项式是一个低误差提取器的$n$位本地源与最小熵$\欧米茄（r（n\log n）^{1/r}）$，我们表明，这是紧。我们的结果利用了几个新的成分，这可能是独立的利益。我们存在的结果依赖于一个新的减少从本地源到一个更结构化的家庭，被称为本地非遗忘位固定源。为了证明它的紧密性，我们证明了Cohen和Tal（RANDOM 2015）的结构结果的“局部版本“，它依赖于一个新的“低权重“Chevalley-Warning定理。
We continue a line of work on extracting random bits from weak sources that are generated by simple processes. We focus on the model of locally samplable sources, where each bit in the source depends on a small number of (hidden) uniformly random input bits. Also known as local sources, this model was introduced by De and Watson (TOCT 2012) and Viola (SICOMP 2014), and is closely related to sources generated by $\mathsf{AC}^0$ circuits and bounded-width branching programs. In particular, extractors for local sources also work for sources generated by these classical computational models. Despite being introduced a decade ago, little progress has been made on improving the entropy requirement for extracting from local sources. The current best explicit extractors require entropy $n^{1/2}$, and follow via a reduction to affine extractors. To start, we prove a barrier showing that one cannot hope to improve this entropy requirement via a black-box reduction of this form. In particular, new techniques are needed. In our main result, we seek to answer whether low-degree polynomials (over $\mathbb{F}_2$) hold potential for breaking this barrier. We answer this question in the positive, and fully characterize the power of low-degree polynomials as extractors for local sources. More precisely, we show that a random degree $r$ polynomial is a low-error extractor for $n$-bit local sources with min-entropy $\Omega(r(n\log n)^{1/r})$, and we show that this is tight. Our result leverages several new ingredients, which may be of independent interest. Our existential result relies on a new reduction from local sources to a more structured family, known as local non-oblivious bit-fixing sources. To show its tightness, we prove a"local version"of a structural result by Cohen and Tal (RANDOM 2015), which relies on a new"low-weight"Chevalley-Warning theorem.