奇偶校验与稀疏度：多项式符号表示的新研究

本文主要探讨了稀疏多项式符号表示的奇偶校验性质及其与稀疏度的关系在计算机科学中的重要性。多项式符号表示是一种将实多项式P(X1, ..., Xn)映射到{0, 1}的函数f，其中P(a1, ..., an)等于(-1)^f(a1, ..., an)。这种方法在计算复杂性理论和计算学习理论中有广泛应用，目标是确定函数f的多项式的最小度和稀疏度，即最小的非零系数数量。 尽管多项式的次数易于理解，但对稀疏性的理解相对有限。现有的界限大多局限于特殊域A={0, 1}或A={-1, +1}。本文的主要贡献在于对任意集合A的符号表示的稀疏度与度之间的关系进行了深入研究。具体来说，作者展示了对于给定的n维多项式，如果其表示集合{0, ..., m-1}中的每个元素且每个变量的最高次数为m-1，那么它的稀疏度至少为mn。这表明，随着度的提高，稀疏度可能会降低。 进一步，作者证明了一个关于奇偶校验函数的下界，即任何在{0, ..., m-1}n上具有(n(m-2)+1)个非零系数的稀疏多项式，其表示奇偶校验的下界。对于任意子集A，文章给出了稀疏性的确切界限。这个结果的应用之一是利用稀疏性的界限来分析电路复杂性，如2-AND-OR-NOT电路的深度。通过这种方法，作者改进了之前关于这类电路阈值门所需电路大小的4n/2的界限，证明了至少需要1.5n的大小来计算奇偶校验函数。 此外，文章还提供了内积函数在{0, 1}n×{0, 1}n上的一个2n的下界，这部分工作得到了NSF职业奖0133597和斯隆基金会奖学金的支持。整个研究揭示了稀疏多项式符号表示在理论和实际应用中的关键作用，特别是在处理复杂问题时，稀疏性作为优化资源分配的关键参数具有重要意义。