期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2016
卷号：2016
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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 MAJ k . We observe that the minimum value of k for which there exists a MAJ k MAJ k circuit that has high correlation with the majority of n bits is equal to ( n 1 2 ) . We then show that for a randomized MAJ k 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 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.
关键词：average case ; circuit complexity ; Correlation ; majority ; threshold ; worst case
