{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T18:01:43Z","timestamp":1781114503321,"version":"3.54.1"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2018,11,29]],"date-time":"2018-11-29T00:00:00Z","timestamp":1543449600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100006769","name":"Russian Science Foundation","doi-asserted-by":"publisher","award":["16-11-10123"],"award-info":[{"award-number":["16-11-10123"]}],"id":[{"id":"10.13039\/501100006769","id-type":"DOI","asserted-by":"publisher"}]},{"name":"MK","award":["MK-5379.2018.1"],"award-info":[{"award-number":["MK-5379.2018.1"]}]},{"name":"Russian Academic Excellence Project \u20195-100\u2019"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2019,7]]},"DOI":"10.1007\/s00224-018-9900-3","type":"journal-article","created":{"date-parts":[[2018,11,28]],"date-time":"2018-11-28T23:37:58Z","timestamp":1543448278000},"page":"956-986","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates"],"prefix":"10.1007","volume":"63","author":[{"given":"Alexander S.","family":"Kulikov","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7154-138X","authenticated-orcid":false,"given":"Vladimir V.","family":"Podolskii","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2018,11,29]]},"reference":[{"issue":"3","key":"9900_CR1","doi-asserted-by":"publisher","first-page":"14:1","DOI":"10.1145\/1706591.1706594","volume":"57","author":"E Allender","year":"2010","unstructured":"Allender, E., Kouck\u00fd, M.: Amplifying lower bounds by means of self-reducibility. J. ACM 57(3), 14:1\u201314:36 (2010)","journal-title":"J. ACM"},{"key":"9900_CR2","doi-asserted-by":"crossref","unstructured":"Amano, K., Yoshida, M.: Depth two (n \u2212\u20092)-majority circuits for n-majority. Preprint (2017)","DOI":"10.1587\/transfun.E101.A.1543"},{"key":"9900_CR3","unstructured":"Bruno, B.: Personal communication (2017)"},{"key":"9900_CR4","first-page":"123","volume":"22","author":"C Xi","year":"2015","unstructured":"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)","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"9900_CR5","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511581274","volume-title":"Concentration of Measure for the Analysis of Randomized Algorithms","author":"DP Dubhashi","year":"2009","unstructured":"Dubhashi, D.P., Panconesi, A.: Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press, Cambridge (2009)"},{"key":"9900_CR6","first-page":"174","volume":"24","author":"C Engels","year":"2017","unstructured":"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)","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"9900_CR7","volume-title":"An Introduction to Probability Theory and Its Applications, vol. 1","author":"W Feller","year":"1968","unstructured":"Feller, W.: An Introduction to Probability Theory and Its Applications, vol. 1. Wiley, New York (1968)"},{"key":"9900_CR8","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1007\/BF01200426","volume":"2","author":"M Goldmann","year":"1992","unstructured":"Goldmann, M., H\u00e5stad, J., Razborov, A.A.: Majority gates vs. general weighted threshold gates. Comput. Complex. 2, 277\u2013300 (1992)","journal-title":"Comput. Complex."},{"key":"9900_CR9","unstructured":"Goldreich, O.: Valiant\u2019s polynomial-size monotone formula for majority, 2001. Available at http:\/\/www.wisdom.weizmann.ac.il\/oded\/PDF\/mono-maj.pdf"},{"key":"9900_CR10","doi-asserted-by":"crossref","unstructured":"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\u201326 (1992)","DOI":"10.1109\/SCT.1992.215377"},{"issue":"2","key":"9900_CR11","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1016\/j.spl.2005.05.019","volume":"75","author":"D Hush","year":"2005","unstructured":"Hush, D., Scovel, C.: Concentration of the hypergeometric distribution. Stat. Probab. Lett. 75(2), 127\u2013132 (2005)","journal-title":"Stat. Probab. Lett."},{"key":"9900_CR12","volume-title":"Extremal Combinatorics - With Applications in Computer Science. Texts in Theoretical Computer Science. An EATCS Series","author":"S Jukna","year":"2011","unstructured":"Jukna, S.: Extremal Combinatorics - With Applications in Computer Science. Texts in Theoretical Computer Science. An EATCS Series. Springer, Berlin (2011)"},{"key":"9900_CR13","volume-title":"Boolean Function Complexity - Advances and Frontiers, volume 27 of Algorithms and Combinatorics","author":"S Jukna","year":"2012","unstructured":"Jukna, S.: Boolean Function Complexity - Advances and Frontiers, volume 27 of Algorithms and Combinatorics. Springer, Berlin (2012)"},{"issue":"4","key":"9900_CR14","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1007\/s000370050005","volume":"8","author":"S Jukna","year":"1999","unstructured":"Jukna, S., Razborov, A.A., Savick\u00fd, P., Wegener, I.: On P versus NP cap co-NP for decision trees and read-once branching programs. Comput. Complex. 8(4), 357\u2013370 (1999)","journal-title":"Comput. Complex."},{"issue":"5","key":"9900_CR15","doi-asserted-by":"publisher","first-page":"1231","DOI":"10.1137\/S0097539705446846","volume":"36","author":"J Kamp","year":"2007","unstructured":"Kamp, J., Zuckerman, D.: Deterministic extractors for bit-fixing sources and exposure-resilient cryptography. SIAM J. Comput. 36(5), 1231\u20131247 (2007)","journal-title":"SIAM J. Comput."},{"key":"9900_CR16","unstructured":"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)"},{"key":"9900_CR17","unstructured":"Kombarov, Y.A.: On depth two circuits for the majority function. In: Proceedings of Problems in theoretical cybernetics, pp 129\u2013132. Max Press (2017)"},{"key":"9900_CR18","unstructured":"Kulikov, A.S., Podolskii, V.V.: Computing majority by constant depth majority circuits with low fan-in gates. In: Vollmer, H., Vall\u00e9e, 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)"},{"issue":"3","key":"9900_CR19","doi-asserted-by":"publisher","first-page":"612","DOI":"10.1002\/rsa.20598","volume":"48","author":"F Magniez","year":"2016","unstructured":"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\u2013638 (2016)","journal-title":"Random Struct. Algorithms"},{"key":"9900_CR20","volume-title":"Perceptrons - An Introduction to Computational Geometry","author":"M Minsky","year":"1987","unstructured":"Minsky, M., Papert, S.: Perceptrons - An Introduction to Computational Geometry. MIT Press, Cambridge (1987)"},{"issue":"3","key":"9900_CR21","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1002\/rsa.10097","volume":"23","author":"E Mossel","year":"2003","unstructured":"Mossel, E., O\u2019Donnell, R.: On the noise sensitivity of monotone functions. Random Struct. Algorithms 23(3), 333\u2013350 (2003)","journal-title":"Random Struct. Algorithms"},{"key":"9900_CR22","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139814782","volume-title":"Analysis of Boolean Functions","author":"R O\u2019Donnell","year":"2014","unstructured":"O\u2019Donnell, R.: Analysis of Boolean Functions. Cambridge University Press, Cambridge (2014)"},{"key":"9900_CR23","unstructured":"Posobin, G.: Computing majority with low-fan-in majority queries. CoRR, arXiv: 1711.10176 (2017)"},{"key":"9900_CR24","volume-title":"An Introduction to the Analysis of Algorithms","author":"R Sedgewick","year":"1996","unstructured":"Sedgewick, R., Flajolet, P.: An Introduction to the Analysis of Algorithms. Addison-Wesley-Longman, Reading (1996)"},{"issue":"1","key":"9900_CR25","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1214\/aos\/1176342611","volume":"2","author":"RJ Serfling","year":"1974","unstructured":"Serfling, R.J.: Probability inequalities for the sum in sampling without replacement. Ann. Stat. 2(1), 39\u201348 (1974)","journal-title":"Ann. Stat."},{"issue":"3","key":"9900_CR26","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1137\/0404038","volume":"4","author":"K-Y Siu","year":"1991","unstructured":"Siu, K.-Y., Bruck, J.: On the power of threshold circuits with small weights. SIAM J. Discrete Math. 4(3), 423\u2013435 (1991)","journal-title":"SIAM J. Discrete Math."},{"issue":"3","key":"9900_CR27","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1016\/0196-6774(84)90016-6","volume":"5","author":"LG Valiant","year":"1984","unstructured":"Valiant, L.G.: Short monotone formulae for the majority function. J. Algorithms 5(3), 363\u2013366 (1984)","journal-title":"J. Algorithms"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-018-9900-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-018-9900-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-018-9900-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T07:00:44Z","timestamp":1775286044000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-018-9900-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,11,29]]},"references-count":27,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2019,7]]}},"alternative-id":["9900"],"URL":"https:\/\/doi.org\/10.1007\/s00224-018-9900-3","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,11,29]]},"assertion":[{"value":"29 November 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}