2026-08-07T10:55:14Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6983 2024-03-06T10:39:14Z ddc:004 open_access

Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates Kulikov, Alexander S. Podolskii, Vladimir V. circuit complexity computational complexity threshold majority lower bound upper bound We study the following computational problem: for which values of k, the majority of n bits MAJ_n can be computed with a depth two formula whose each gate computes a majority function of at most k bits? The corresponding computational model is denoted by MAJ_k o MAJ_k. We observe that the minimum value of k for which there exists a MAJ_k o MAJ_k circuit that has high correlation with the majority of n bits is equal to Theta(sqrt(n)). We then show that for a randomized MAJ_k o MAJ_k circuit computing the majority of n input bits with high probability for every input, the minimum value of k is equal to n^(2/3+o(1)). We show a worst case lower bound: if a MAJ_k o MAJ_k circuit computes the majority of n bits correctly on all inputs, then k <= n^(13/19+o(1)). This lower bound exceeds the optimal value for randomized circuits and thus is unreachable for pure randomized techniques. For depth 3 circuits we show that a circuit with k= O(n^(2/3)) can compute MAJ_n correctly on all inputs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Alexander S. Kulikov and Vladimir V. Podolskii 2017 Is Part Of LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2017.49 urn:nbn:de:0030-drops-69832 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.49 eng https://creativecommons.org/licenses/by/3.0/legalcode