×

Computing majority by constant depth majority circuits with low fan-in gates. (English) Zbl 1429.68082

Summary: We study the following computational problem: for which values of \(k\), the majority of \(n\) bits \(\mathrm{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 \(\mathrm{MAJ}_k \circ \mathrm{MAJ}_k\). We observe that the minimum value of \(k\) for which there exists a \(\mathrm{MAJ}_k\circ \mathrm{MAJ}_k\) circuit that has high correlation with the majority of \(n\) bits is equal to \(\Theta(n^{1/2})\). We then show that for a randomized \(\mathrm{MAJ}_k\circ \mathrm{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 \(\mathrm{MAJ}_k \circ \mathrm{MAJ}_k\) circuit computes the majority of \(n\) bits correctly on all inputs, then \(k \geq n^{13/19 + o(1)}\).

MSC:

68Q25 Analysis of algorithms and problem complexity
68Q06 Networks and circuits as models of computation; circuit complexity
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68W20 Randomized algorithms
94C11 Switching theory, applications of Boolean algebras to circuits and networks
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Allender, E., Koucký, M.: Amplifying lower bounds by means of self-reducibility. J. ACM 57(3), 14:1-14:36 (2010) · Zbl 1327.68112 · doi:10.1145/1706591.1706594
[2] Amano, K., Yoshida, M.: Depth two (n − 2)-majority circuits for n-majority. Preprint (2017)
[3] Bruno, B.: Personal communication (2017)
[4] Xi, C., Oliveira, I.C., Servedio, R.A.: Addition is exponentially harder than counting for shallow monotone circuits. Electronic Colloquium on Computational Complexity (ECCC) 22, 123 (2015)
[5] Dubhashi, D.P., Panconesi, A.: Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press, Cambridge (2009) · Zbl 1213.60006 · doi:10.1017/CBO9780511581274
[6] Engels, C., Garg, M., Makino, K., Rao, A.: On expressing majority as a majority of majorities. Electronic Colloquium on Computational Complexity (ECCC) 24, 174 (2017)
[7] Feller, W.: An Introduction to Probability Theory and Its Applications, vol. 1. Wiley, New York (1968) · Zbl 0155.23101
[8] Goldmann, M., Håstad, J., Razborov, A.A.: Majority gates vs. general weighted threshold gates. Comput. Complex. 2, 277-300 (1992) · Zbl 0770.68054 · doi:10.1007/BF01200426
[9] Goldreich, O.: Valiant’s polynomial-size monotone formula for majority, 2001. Available at http://www.wisdom.weizmann.ac.il/oded/PDF/mono-maj.pdf · Zbl 07578380
[10] Hofmeister, T.: The power of negative thinking in constructing threshold circuits for addition. In: Proceedings of the Seventh Annual Structure in Complexity Theory Conference, Boston, Massachusetts, USA, June 22-25, 1992, pp 20-26 (1992)
[11] Hush, D., Scovel, C.: Concentration of the hypergeometric distribution. Stat. Probab. Lett. 75(2), 127-132 (2005) · Zbl 1284.60032 · doi:10.1016/j.spl.2005.05.019
[12] Jukna, S.: Extremal Combinatorics - With Applications in Computer Science. Texts in Theoretical Computer Science. An EATCS Series. Springer, Berlin (2011) · Zbl 1239.05001
[13] Jukna, S.: Boolean Function Complexity - Advances and Frontiers, volume 27 of Algorithms and Combinatorics. Springer, Berlin (2012) · Zbl 1235.94005
[14] Jukna, S., Razborov, A.A., Savický, P., Wegener, I.: On P versus NP cap co-NP for decision trees and read-once branching programs. Comput. Complex. 8(4), 357-370 (1999) · Zbl 0962.68075 · doi:10.1007/s000370050005
[15] Kamp, J., Zuckerman, D.: Deterministic extractors for bit-fixing sources and exposure-resilient cryptography. SIAM J. Comput. 36(5), 1231-1247 (2007) · Zbl 1124.68036 · doi:10.1137/S0097539705446846
[16] Kane, D.M., Williams, R.: Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits. In: Wichs, D., Mansour, Y. (eds.) Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pp 633-643 (2016) · Zbl 1373.68220
[17] Kombarov, Y.A.: On depth two circuits for the majority function. In: Proceedings of Problems in theoretical cybernetics, pp 129-132. Max Press (2017)
[18] Kulikov, A.S., Podolskii, V.V.: Computing majority by constant depth majority circuits with low fan-in gates. In: Vollmer, H., Vallée, B. (eds.) 34th Symposium on Theoretical Aspects of Computer Science, STACS 2017, March 8-11 Hannover, Germany, volume 66 of LIPIcs, p 2017. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2017) · Zbl 1402.68100
[19] Magniez, F., Nayak, A., Santha, M., Sherman, J., Tardos, G., Xiao, D.: Improved bounds for the randomized decision tree complexity of recursive majority. Random Struct. Algorithms 48(3), 612-638 (2016) · Zbl 1338.05250 · doi:10.1002/rsa.20598
[20] Minsky, M., Papert, S.: Perceptrons - An Introduction to Computational Geometry. MIT Press, Cambridge (1987) · Zbl 0197.43702
[21] Mossel, E., O’Donnell, R.: On the noise sensitivity of monotone functions. Random Struct. Algorithms 23(3), 333-350 (2003) · Zbl 1047.68106 · doi:10.1002/rsa.10097
[22] O’Donnell, R.: Analysis of Boolean Functions. Cambridge University Press, Cambridge (2014) · Zbl 1336.94096 · doi:10.1017/CBO9781139814782
[23] Posobin, G.: Computing majority with low-fan-in majority queries. CoRR, arXiv:1711.10176 (2017)
[24] Sedgewick, R., Flajolet, P.: An Introduction to the Analysis of Algorithms. Addison-Wesley-Longman, Reading (1996) · Zbl 0841.68059
[25] Serfling, R.J.: Probability inequalities for the sum in sampling without replacement. Ann. Stat. 2(1), 39-48 (1974) · Zbl 0288.62005 · doi:10.1214/aos/1176342611
[26] Siu, K.-Y., Bruck, J.: On the power of threshold circuits with small weights. SIAM J. Discrete Math. 4(3), 423-435 (1991) · Zbl 0737.68035 · doi:10.1137/0404038
[27] Valiant, L.G.: Short monotone formulae for the majority function. J. Algorithms 5(3), 363-366 (1984) · Zbl 0554.94017 · doi:10.1016/0196-6774(84)90016-6
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.