Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
Computing majority by constant depth majority circuits with low fan-in gates. / Kulikov, Alexander S.; Podolskii, Vladimir V.
34th Symposium on Theoretical Aspects of Computer Science, STACS 2017. ed. / Brigitte Vallee; Heribert Vollmer. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2017. 49 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 66).Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
}
TY - GEN
T1 - Computing majority by constant depth majority circuits with low fan-in gates
AU - Kulikov, Alexander S.
AU - Podolskii, Vladimir V.
PY - 2017/3/1
Y1 - 2017/3/1
N2 - We study the following computational problem: for which values of k, the majority of n bits MAJn 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 MAJk o MAJk. We observe that the minimum value of k for which there exists a MAJk o MAJk circuit that has high correlation with the majority of n bits is equal to Θ(n1/2). We then show that for a randomized MAJk o MAJk circuit computing the majority of n input bits with high probability for every input, the minimum value of k is equal to n2/3+o(1). We show a worst case lower bound: if a MAJk o MAJk circuit computes the majority of n bits correctly on all inputs, then k ≥ n13/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(n2/3) can compute MAJn correctly on all inputs.
AB - We study the following computational problem: for which values of k, the majority of n bits MAJn 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 MAJk o MAJk. We observe that the minimum value of k for which there exists a MAJk o MAJk circuit that has high correlation with the majority of n bits is equal to Θ(n1/2). We then show that for a randomized MAJk o MAJk circuit computing the majority of n input bits with high probability for every input, the minimum value of k is equal to n2/3+o(1). We show a worst case lower bound: if a MAJk o MAJk circuit computes the majority of n bits correctly on all inputs, then k ≥ n13/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(n2/3) can compute MAJn correctly on all inputs.
KW - Circuit complexity
KW - Computational complexity
KW - Lower bound
KW - Majority
KW - Threshold
KW - Upper bound
UR - http://www.scopus.com/inward/record.url?scp=85016194461&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.STACS.2017.49
DO - 10.4230/LIPIcs.STACS.2017.49
M3 - Conference contribution
AN - SCOPUS:85016194461
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 34th Symposium on Theoretical Aspects of Computer Science, STACS 2017
A2 - Vallee, Brigitte
A2 - Vollmer, Heribert
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 34th Symposium on Theoretical Aspects of Computer Science, STACS 2017
Y2 - 8 March 2017 through 11 March 2017
ER -
ID: 49820870