Kulikov, Alexander S. ;
Podolskii, Vladimir V.
Computing Majority by Constant Depth Majority Circuits with Low Fanin Gates
Abstract
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.
BibTeX  Entry
@InProceedings{kulikov_et_al:LIPIcs:2017:6983,
author = {Alexander S. Kulikov and Vladimir V. Podolskii},
title = {{Computing Majority by Constant Depth Majority Circuits with Low Fanin Gates}},
booktitle = {34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
pages = {49:149:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770286},
ISSN = {18688969},
year = {2017},
volume = {66},
editor = {Heribert Vollmer and Brigitte Vallée},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/6983},
URN = {urn:nbn:de:0030drops69832},
doi = {10.4230/LIPIcs.STACS.2017.49},
annote = {Keywords: circuit complexity, computational complexity, threshold, majority, lower bound, upper bound}
}
2017
Keywords: 

circuit complexity, computational complexity, threshold, majority, lower bound, upper bound 
Seminar: 

34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)

Issue date: 

2017 
Date of publication: 

2017 