标题： k个相互独立的位都为1的最大概率 显示英文标题

标题： The Maximal Probability that k-wise Independent Bits are All 1

摘要： k-wise独立的n位分布是位的联合分布，使得其中任意k个位都是独立的。 在本文中，我们考虑具有相同边缘分布的k-wise独立分布，每个位为1的概率为p。 我们研究以下问题：对于这样的分布，所有位都为1的概率可能有多大？ 对于参数n、k和p的广泛范围，我们找到了该概率的一个显式下界，该下界与Benjamini等人给出的上界在低阶乘数因子范围内一致。 我们研究的问题可以看作是纠错码理论中一个主要开放问题的松弛，即给定参数下线性纠错码能有多大？ 这个问题是一种离散矩问题，我们的方法基于证明从经典矩问题理论中得到的界限对该问题提供了良好的近似。 我们使用的主要工具是一个控制多项式零点经过小扰动后期望变化的界限。 显示英文摘要

摘要： A k-wise independent distribution on n bits is a joint distribution of the bits such that each k of them are independent. In this paper we consider k-wise independent distributions with identical marginals, each bit has probability p to be 1. We address the following question: how high can the probability that all the bits are 1 be, for such a distribution? For a wide range of the parameters n,k and p we find an explicit lower bound for this probability which matches an upper bound given by Benjamini et al., up to multiplicative factors of lower order. The question we investigate can be seen as a relaxation of a major open problem in error-correcting codes theory, namely, how large can a linear error correcting code with given parameters be? The question is a type of discrete moment problem, and our approach is based on showing that bounds obtained from the theory of the classical moment problem provide good approximations for it. The main tool we use is a bound controlling the change in the expectation of a polynomial after small perturbation of its zeros.