论文标题
比较低于多数的计算熵（OR：何时密集模型定理false？）
Comparing computational entropies below majority (or: When is the dense model theorem false?)
论文作者
论文摘要
计算伪随机研究研究随机变量$ \ bf {z} $在多大程度上，根据一类测试的统一分布$ \ cal {f} $。计算熵通过研究随机变量看起来像\ emph {高熵}分布的程度，从而概括了计算伪界。计算熵有不同的形式定义，对于不同的应用，具有不同的优势。因此，了解这些定义等于何时是有意思的。 我们考虑三个计算熵概念，当测试类别$ \ cal {f} $在多数情况下关闭时，它们已知等效。这种等效性构成了绿色和道的所谓\ emph {密集模型定理}（后来由Tao-Zeigler，Reingold等人和Gowers明确说明）。密集的模型定理在绿色和道的证据中起着关键作用，证明素数包含任意长的算术进程，此后与数学和计算机科学的令人惊讶的广泛主题相连，包括加密性，计算复杂性，组合方法和机器学习。我们表明，在不同情况下，$ \ cal {f} $是\ emph {not}在多数情况下关闭的，此等价失败了。反过来，这提供了密集模型定理为\ emph {false}的示例。
Computational pseudorandomness studies the extent to which a random variable $\bf{Z}$ looks like the uniform distribution according to a class of tests $\cal{F}$. Computational entropy generalizes computational pseudorandomness by studying the extent which a random variable looks like a \emph{high entropy} distribution. There are different formal definitions of computational entropy with different advantages for different applications. Because of this, it is of interest to understand when these definitions are equivalent. We consider three notions of computational entropy which are known to be equivalent when the test class $\cal{F}$ is closed under taking majorities. This equivalence constitutes (essentially) the so-called \emph{dense model theorem} of Green and Tao (and later made explicit by Tao-Zeigler, Reingold et al., and Gowers). The dense model theorem plays a key role in Green and Tao's proof that the primes contain arbitrarily long arithmetic progressions and has since been connected to a surprisingly wide range of topics in mathematics and computer science, including cryptography, computational complexity, combinatorics and machine learning. We show that, in different situations where $\cal{F}$ is \emph{not} closed under majority, this equivalence fails. This in turn provides examples where the dense model theorem is \emph{false}.
