License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2023.43
URN: urn:nbn:de:0030-drops-175468
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/17546/
Dobrokhotova-Maikova, Natalia ;
Kozachinskiy, Alexander ;
Podolskii, Vladimir
Constant-Depth Sorting Networks
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 fan-in.
Motivated by these questions, we initiate the studies of lower bounds for constant-depth 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 = {Dobrokhotova-Maikova, Natalia and Kozachinskiy, Alexander and Podolskii, Vladimir},
title = {{Constant-Depth Sorting Networks}},
booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
pages = {43:1--43:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-263-1},
ISSN = {1868-8969},
year = {2023},
volume = {251},
editor = {Tauman Kalai, Yael},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/17546},
URN = {urn:nbn:de:0030-drops-175468},
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 |
