论文标题
决策清单的多项式阈值函数
Polynomial Threshold Functions for Decision Lists
论文作者
论文摘要
For $S \subseteq \{0,1\}^n$ a Boolean function $f \colon S \to \{-1,1\}$ is a polynomial threshold function (PTF) of degree $d$ and weight $W$ if there is a polynomial $p$ with integer coefficients of degree $d$ and with sum of absolute coefficients $W$ such that $ f（x）= \ text {sign}（p（x））$ in s $中的所有$ x \。我们研究决策列表的表示形式为ptfs，布尔立方体$ \ {0,1 \}^n $以及锤击球$ \ {0,1 \}^{n} _ {\ leq k} $。 作为我们的第一个结果，我们证明了所有$ d = o \ left（\ left（\ frac {n} {\ log n} \ right）^{1/3} \ right）$ $ \ {0,1 \}^n $上的任何决策列表可以由$ d $ $ d $ $ d $和$ d $ $ d $ $ d $ $ d $ $ d $和$ 2^$ n/d/d/d/d/n/d/d/d $表示。这改善了Klivans and Ferveio [Klivans，Serveio，2006]的结果，在体重指数中的$ \ log^2 d $因素。对于所有$ d = o \ left（\ left（\ frac {n} {\ log n} \ right）^{1/3} \ right）$，我们的界限都是紧密的（\ frac {n} {\ log n} \ right）^{1/3} \ right）$。 对于锤子球$ \ {0,1 \}^n _ {\ leq k} $的决策列表，我们表明，上面的上面的上限可以大大改进到$ n^{o（\ sqrt {k} {k} {k}} $ $ d =θ（\ sqrt {\ sqrt {k k}）$。我们还证明，对于所有$ d = o（\ sqrt {k}）$，通过证明下限$ w = 2^{ω（n/d^2）} $，不可能进行类似的改进。 \ end {摘要}
For $S \subseteq \{0,1\}^n$ a Boolean function $f \colon S \to \{-1,1\}$ is a polynomial threshold function (PTF) of degree $d$ and weight $W$ if there is a polynomial $p$ with integer coefficients of degree $d$ and with sum of absolute coefficients $W$ such that $f(x) = \text{sign}(p(x))$ for all $x \in S$. We study a representation of decision lists as PTFs over Boolean cubes $\{0,1\}^n$ and over Hamming balls $\{0,1\}^{n}_{\leq k}$. As our first result, we show that for all $d = O\left( \left( \frac{n}{\log n}\right)^{1/3}\right)$ any decision list over $\{0,1\}^n$ can be represented by a PTF of degree $d$ and weight $2^{O(n/d^2)}$. This improves the result by Klivans and Servedio [Klivans, Servedio, 2006] by a $\log^2 d$ factor in the exponent of the weight. Our bound is tight for all $d = O\left( \left( \frac{n}{\log n}\right)^{1/3}\right)$ due to the matching lower bound by Beigel [Beigel, 1994]. For decision lists over a Hamming ball $\{0,1\}^n_{\leq k}$ we show that the upper bound on weight above can be drastically improved to $n^{O(\sqrt{k})}$ for $d = Θ(\sqrt{k})$. We also show that similar improvement is not possible for smaller degrees by proving the lower bound $W = 2^{Ω(n/d^2)}$ for all $d = O(\sqrt{k})$. \end{abstract}
