2026-07-21T19:38:35Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:21043 2024-09-16T06:02:39Z ddc:004 open_access

Towards Simpler Sorting Networks and Monotone Circuits for Majority Dobrokhotova-Maikova, Natalia Kozachinskiy, Alexander Podolskii, Vladimir Sorting networks constant depth lower bounds threshold circuits 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Natalia Dobrokhotova-Maikova and Alexander Kozachinskiy and Vladimir Podolskii 2024 Is Part Of LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2024.50 urn:nbn:de:0030-drops-210436 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.50 eng https://creativecommons.org/licenses/by/4.0/legalcode