1 Search Results for "Dobrokhotova-Maikova, Natalia"

Document

DOI: 10.4230/LIPIcs.ITCS.2023.43

Constant-Depth Sorting Networks

Authors: Natalia Dobrokhotova-Maikova, Alexander Kozachinskiy, and Vladimir Podolskii

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

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.

Cite as

Natalia Dobrokhotova-Maikova, Alexander Kozachinskiy, and Vladimir Podolskii. Constant-Depth Sorting Networks. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 43:1-43:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.43},
  URN =		{urn:nbn:de:0030-drops-175468},
  doi =		{10.4230/LIPIcs.ITCS.2023.43},
  annote =	{Keywords: Sorting networks, constant depth, lower bounds, threshold circuits}
}

Refine by Author
1 Dobrokhotova-Maikova, Natalia
1 Kozachinskiy, Alexander
1 Podolskii, Vladimir

Refine by Classification
1 Theory of computation → Models of computation

Refine by Keyword
1 Sorting networks
1 constant depth
1 lower bounds
1 threshold circuits

Refine by Type
1 document

Refine by Publication Year
1 2023

1 Search Results for "Dobrokhotova-Maikova, Natalia"

Constant-Depth Sorting Networks

Abstract

Cite as

Thanks for your feedback!

Could not send message