论文标题
恒定深入分类网络
Constant-Depth Sorting Networks
论文作者
论文摘要
在本文中，我们解决了从Arity $ K> 2 $的比较器构建的分类网络。也就是说，在我们的设置中，比较器的差异 - 或换句话说，可以按单位成本进行排序的输入数量 - 是一个参数。我们研究了它与其他两个参数的关系 - $ n $，输入的数量和$ d $，深度。 该模型受到了很大的关注。部分原因是它的动机是更好地了解分类网络的结构。特别是，具有较大ARITH的分类网络与普通分类网络的递归结构有关。此外，对该模型的研究具有自然的对应关系，该研究最新的工作是从较低粉丝的多数门中构建多数功能的电路。 在这些问题的激励下，我们获得了关于恒定分类网络的ARITY的第一个下限。更确切地说，我们考虑将深度$ d $ 4的网络排序最高4，并确定具有与Arity $ K $比较的网络的最小$ K $。对于深度$ d = 1,2 $，我们观察到$ k = n $。对于$ d = 3 $，我们表明$ k = \ lceil \ frac n2 \ rceil $。对于$ d = 4 $，最小值变为sublinear：$ k =θ（n^{2/3}）$。这与多数电路的情况形成鲜明对比，其中$ k = o（n^{2/3}）$对于深度$ d = 3 $就可以实现。
In this paper, we address sorting networks that are constructed from comparators of arity $k > 2$. That is, in our setting the arity of the comparators -- or, in other words, the number of inputs that can be sorted at the unit cost -- is a parameter. We study its relationship with two other parameters -- $n$, the number of inputs, and $d$, the depth. This model received considerable attention. Partly, its motivation is to better understand the structure of sorting networks. In particular, sorting networks with large arity are related to recursive constructions of ordinary sorting networks. Additionally, studies of this model have natural correspondence with a recent line of work on constructing circuits for majority functions from majority gates of lower fan-in. Motivated by these questions, we obtain the first lower bounds on the arity of constant-depth sorting networks. More precisely, we consider sorting networks of depth $d$ up to 4, and determine the minimal $k$ for which there is such a network with comparators of arity $k$. For depths $d=1,2$ we observe that $k=n$. For $d=3$ we show that $k = \lceil \frac n2 \rceil$. For $d=4$ the minimal arity becomes sublinear: $k = Θ(n^{2/3})$. This contrasts with the case of majority circuits, in which $k = O(n^{2/3})$ is achievable already for depth $d=3$.
