论文标题
在多项式阈值函数的重量和密度边界上
On the weight and density bounds of polynomial threshold functions
论文作者
论文摘要
在本报告中，我们显示所有N-变量的布尔函数都可以表示为多项式阈值函数（PTF），最多$ 0.75 \ times 2^n $非零整数系数，并在这些系数的绝对值上给出上限。据我们所知，这提供了一般布尔函数的PTF密度（单次数量）和重量（系数幅度之和）的最著名结合。还分析了弯曲函数的特殊情况，并表明可以用小于$ 2^n $的整数系数表示任何N-变量弯曲函数，同时也遵守上述密度结合。最后，稀疏的布尔函数几乎是恒定的，除了$ m << 2^n $可变分配数量，显示具有较小的重量PTF，最多$ m+2^{n-1} $。
In this report, we show that all n-variable Boolean function can be represented as polynomial threshold functions (PTF) with at most $0.75 \times 2^n$ non-zero integer coefficients and give an upper bound on the absolute value of these coefficients. To our knowledge this provides the best known bound on both the PTF density (number of monomials) and weight (sum of the coefficient magnitudes) of general Boolean functions. The special case of Bent functions is also analyzed and shown that any n-variable Bent function can be represented with integer coefficients less than $2^n$ while also obeying the aforementioned density bound. Finally, sparse Boolean functions, which are almost constant except for $m << 2^n$ number of variable assignments, are shown to have small weight PTFs with density at most $m+2^{n-1}$.
