DROPS

Document

RANDOM

DOI: 10.4230/LIPIcs.APPROX/RANDOM.2024.50

Towards Simpler Sorting Networks and Monotone Circuits for Majority

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

Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)

Abstract

In this paper, we study the problem of computing the majority function by low-depth monotone circuits and a related problem of constructing low-depth sorting networks. We consider both the classical setting with elementary operations of arity 2 and the generalized setting with operations of arity k, where k is a parameter. For both problems and both settings, there are various constructions known, the minimal known depth being logarithmic. However, there is currently no known efficient deterministic construction that simultaneously achieves sub-log-squared depth, simplicity, and has a potential to be used in practice. In this paper we make progress towards resolution of this problem. For computing majority by standard monotone circuits (gates of arity 2) we provide an explicit monotone circuit of depth O(log₂^{5/3} n). The construction is a combination of several known and not too complicated ideas. Essentially, for this result we gradually derandomize the construction of Valiant (1984). As one of the intermediate steps in our result we need an efficient construction of a sorting network with gates of arity k for arbitrary fixed k. For this we provide a new sorting network architecture inspired by representation of inputs as a high-dimensional cube. As a result we obtain a simple construction that improves previous upper bound of 4 log_k² n to 2 log_k² n. We prove the similar bound for the depth of the circuit computing majority of n bits consisting of gates computing majority of k bits. Note, that for both problems there is an explicit construction of depth O(log_k n) known, but the construction is complicated and the constant hidden in O-notation is huge.

Cite as

Natalia Dobrokhotova-Maikova, Alexander Kozachinskiy, and Vladimir Podolskii. Towards Simpler Sorting Networks and Monotone Circuits for Majority. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 50:1-50:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{dobrokhotovamaikova_et_al:LIPIcs.APPROX/RANDOM.2024.50,
  author =	{Dobrokhotova-Maikova, Natalia and Kozachinskiy, Alexander and Podolskii, Vladimir},
  title =	{{Towards Simpler Sorting Networks and Monotone Circuits for Majority}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)},
  pages =	{50:1--50:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-348-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{317},
  editor =	{Kumar, Amit and Ron-Zewi, Noga},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.50},
  URN =		{urn:nbn:de:0030-drops-210436},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2024.50},
  annote =	{Keywords: Sorting networks, constant depth, lower bounds, threshold circuits}
}

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.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}
}

Search Results

Documents authored by Dobrokhotova-Maikova, Natalia

Towards Simpler Sorting Networks and Monotone Circuits for Majority

Abstract

Cite as

Constant-Depth Sorting Networks

Abstract

Cite as

Thanks for your feedback!

Could not send message