Abstract
In this paper, we address sorting networks that are constructed from comparators of arity k > 2. I.e., 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 fanin.
Motivated by these questions, we initiate the studies of lower bounds for constantdepth sorting networks. More precisely, we consider sorting networks of constant depth d and estimate the minimal k for which there is such a network with comparators of arity k. We prove tight lower bounds for d ≤ 4. More precisely, for depths d = 1,2 we observe that k = n. For d = 3 we show that k = ⌈n/2⌉. As our main result, we show that 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. To prove these results, we develop a new combinatorial technique based on the notion of access to cells of a sorting network.
BibTeX  Entry
@InProceedings{dobrokhotovamaikova_et_al:LIPIcs.ITCS.2023.43,
author = {DobrokhotovaMaikova, Natalia and Kozachinskiy, Alexander and Podolskii, Vladimir},
title = {{ConstantDepth Sorting Networks}},
booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
pages = {43:143:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772631},
ISSN = {18688969},
year = {2023},
volume = {251},
editor = {Tauman Kalai, Yael},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/17546},
URN = {urn:nbn:de:0030drops175468},
doi = {10.4230/LIPIcs.ITCS.2023.43},
annote = {Keywords: Sorting networks, constant depth, lower bounds, threshold circuits}
}
Keywords: 

Sorting networks, constant depth, lower bounds, threshold circuits 
Collection: 

14th Innovations in Theoretical Computer Science Conference (ITCS 2023) 
Issue Date: 

2023 
Date of publication: 

01.02.2023 