论文标题
布尔函数最近的邻居表示
Nearest neighbor representations of Boolean functions
论文作者
论文摘要
布尔函数的最接近的邻域表示是$ r^n $中的一组正和负原型，使得该函数在输入上具有值1，即最接近的原型为正。对于$ k $ neart的邻居表示，考虑了$ k $最接近原型的多数分类。布尔函数的最接近的邻居复杂性是表示该函数所需的原型数量最少。我们为此措施提供了几个范围。在原型可能是真实或需要布尔的情况下，给出了分离。奇偶校验的复杂性是准确确定的。给出了Mod 2内部产品的指数下限，并为其$ k $ neart的邻居复杂性提供了线性下限。使用与其他模型的连接（例如$ \ {1，2 \} $上的多项式阈值函数）证明了结果。我们还讨论了引起的许多开放问题中的一些。
A nearest neighbor representation of a Boolean function is a set of positive and negative prototypes in $R^n$ such that the function has value 1 on an input iff the closest prototype is positive. For $k$-nearest neighbor representation the majority classification of the $k$ closest prototypes is considered. The nearest neighbor complexity of a Boolean function is the minimal number of prototypes needed to represent the function. We give several bounds for this measure. Separations are given between the cases when prototypes can be real or are required to be Boolean. The complexity of parity is determined exactly. An exponential lower bound is given for mod 2 inner product, and a linear lower bound is given for its $k$-nearest neighbor complexity. The results are proven using connections to other models such as polynomial threshold functions over $\{1, 2\}$. We also discuss some of the many open problems arising.
