{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,19]],"date-time":"2026-02-19T07:23:53Z","timestamp":1771485833194,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642151545","type":"print"},{"value":"9783642151552","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-15155-2_8","type":"book-chapter","created":{"date-parts":[[2010,8,13]],"date-time":"2010-08-13T20:17:45Z","timestamp":1281730665000},"page":"66-77","source":"Crossref","is-referenced-by-count":12,"title":["Weights of Exact Threshold Functions"],"prefix":"10.1007","author":[{"given":"L\u00e1szl\u00f3","family":"Babai","sequence":"first","affiliation":[]},{"given":"Kristoffer Arnsfelt","family":"Hansen","sequence":"additional","affiliation":[]},{"given":"Vladimir V.","family":"Podolskii","sequence":"additional","affiliation":[]},{"given":"Xiaoming","family":"Sun","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"1-2","key":"8_CR1","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1016\/0304-3975(95)00073-9","volume":"158","author":"M. Agrawal","year":"1996","unstructured":"Agrawal, M., Arvind, V.: Geometric sets of low information content. Theoretical Computer Science\u00a0158(1-2), 193\u2013219 (1996)","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"8_CR2","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1006\/jcta.1997.2780","volume":"79","author":"N. Alon","year":"1997","unstructured":"Alon, N., V\u0169, V.H.: Anti-hadamard matrices, coin weighing, threshold gates, and indecomposable hypergraphs. Journal of Combinatorial Theory, Series A\u00a079(1), 133\u2013160 (1997)","journal-title":"Journal of Combinatorial Theory, Series A"},{"issue":"4","key":"8_CR3","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1007\/BF01263422","volume":"4","author":"R. Beigel","year":"1994","unstructured":"Beigel, R.: Perceptrons, PP, and the polynomial hierarchy. Computational Complexity\u00a04(4), 339\u2013349 (1994)","journal-title":"Computational Complexity"},{"key":"8_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"420","DOI":"10.1007\/3-540-56279-6_94","volume-title":"Algorithms and Computation","author":"R. Beigel","year":"1992","unstructured":"Beigel, R., Tarui, J., Toda, S.: On probabilistic ACC circuits with an exact-threshold output gate. In: Ibaraki, T., Iwama, K., Yamashita, M., Inagaki, Y., Nishizeki, T. (eds.) ISAAC 1992. LNCS, vol.\u00a0650, pp. 420\u2013429. Springer, Heidelberg (1992)"},{"key":"8_CR5","volume-title":"Problems in Higher Algebra","author":"D.K. Faddeev","year":"1965","unstructured":"Faddeev, D.K., Sominskii, I.S.: Problems in Higher Algebra. W.H. Freeman, New York (1965)"},{"issue":"1","key":"8_CR6","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1007\/PL00001599","volume":"9","author":"F. Green","year":"2000","unstructured":"Green, F.: A complex-number fourier technique for lower bounds on the mod-m degree. Computational Complexity\u00a09(1), 16\u201338 (2000)","journal-title":"Computational Complexity"},{"key":"8_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"448","DOI":"10.1007\/978-3-540-73545-8_44","volume-title":"Computing and Combinatorics","author":"K.A. Hansen","year":"2007","unstructured":"Hansen, K.A.: Computing symmetric boolean functions by circuits with few exact threshold gates. In: Lin, G. (ed.) COCOON 2007. LNCS, vol.\u00a04598, pp. 448\u2013458. Springer, Heidelberg (2007)"},{"key":"8_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1007\/978-3-642-03351-3_13","volume-title":"Computer Science - Theory and Applications","author":"K.A. Hansen","year":"2009","unstructured":"Hansen, K.A.: Depth reduction for circuits with a single layer of modular counting gates. In: Frid, A., Morozov, A., Rybalchenko, A., Wagner, K.W. (eds.) Computer Science - Theory and Applications. LNCS, vol.\u00a05675, pp. 117\u2013128. Springer, Heidelberg (2009)"},{"key":"8_CR9","first-page":"270","volume-title":"Proceedings of the 25th Annual IEEE Conference on Computational Complexity","author":"K.A. Hansen","year":"2010","unstructured":"Hansen, K.A., Podolskii, V.V.: Exact threshold circuits. In: Proceedings of the 25th Annual IEEE Conference on Computational Complexity, pp. 270\u2013279. IEEE Computer Society, Los Alamitos (2010)"},{"key":"8_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1007\/978-3-540-73545-8_15","volume-title":"Computing and Combinatorics","author":"R.C. Harkins","year":"2007","unstructured":"Harkins, R.C., Hitchcock, J.M.: Dimension, halfspaces, and the density of hard sets. In: Lin, G. (ed.) COCOON 2007. LNCS, vol.\u00a04598, pp. 129\u2013139. Springer, Heidelberg (2007)"},{"issue":"3","key":"8_CR11","doi-asserted-by":"publisher","first-page":"484","DOI":"10.1137\/S0895480192235878","volume":"7","author":"J. H\u00e5stad","year":"1994","unstructured":"H\u00e5stad, J.: On the size of weights for threshold gates. SIAM Journal on Discrete Mathematics\u00a07(3), 484\u2013492 (1994)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"8_CR12","volume-title":"Introduction to the Theory of Neural Computation","author":"J. Hertz","year":"1991","unstructured":"Hertz, J., Krogh, A., Palmer, R.G.: Introduction to the Theory of Neural Computation. Addison-Wesley Publishing Company, Reading (1991)"},{"key":"8_CR13","doi-asserted-by":"publisher","first-page":"376","DOI":"10.1016\/0016-0032(61)90702-5","volume":"271","author":"S. Muroga","year":"1961","unstructured":"Muroga, S., Toda, I., Takasu, S.: Theory of majority decision elements. Journal of the Franklin Institute\u00a0271, 376\u2013418 (1961)","journal-title":"Journal of the Franklin Institute"},{"key":"8_CR14","volume-title":"Threshold Logic and its Applications","author":"S. Muroga","year":"1971","unstructured":"Muroga, S.: Threshold Logic and its Applications. John Wiley & Sons, Inc., Chichester (1971)"},{"key":"8_CR15","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/1836.001.0001","volume-title":"Circuit Complexity and Neural Networks","author":"I. Parberry","year":"1994","unstructured":"Parberry, I.: Circuit Complexity and Neural Networks. MIT Press, Cambridge (1994)"},{"key":"8_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1007\/978-3-540-79709-8_27","volume-title":"Computer Science \u2013 Theory and Applications","author":"V.V. Podolskii","year":"2008","unstructured":"Podolskii, V.V.: A uniform lower bound on weights of perceptrons. In: Hirsch, E.A., Razborov, A.A., Semenov, A., Slissenko, A. (eds.) Computer Science \u2013 Theory and Applications. LNCS, vol.\u00a05010, pp. 261\u2013272. Springer, Heidelberg (2008)"},{"issue":"1","key":"8_CR17","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1134\/S0032946009010062","volume":"45","author":"V.V. Podolskii","year":"2009","unstructured":"Podolskii, V.V.: Perceptrons of large weight. Problems of Information Transmission\u00a045(1), 46\u201353 (2009)","journal-title":"Problems of Information Transmission"},{"issue":"6","key":"8_CR18","doi-asserted-by":"publisher","first-page":"368","DOI":"10.1109\/PGEC.1966.264494","volume":"15","author":"D.R. Smith","year":"1966","unstructured":"Smith, D.R.: Bounds on the number of threshold functions. IEEE Transactions on Electronic Computers EC\u00a015(6), 368\u2013369 (1966)","journal-title":"IEEE Transactions on Electronic Computers EC"},{"issue":"6","key":"8_CR19","doi-asserted-by":"publisher","first-page":"926","DOI":"10.1109\/PGEC.1965.264090","volume":"14","author":"S. Yajima","year":"1965","unstructured":"Yajima, S., Ibaraki, T.: A lower bound on the number of threshold functions. IEEE Transactions on Electronic Computers EC\u00a014(6), 926\u2013929 (1965)","journal-title":"IEEE Transactions on Electronic Computers EC"},{"key":"8_CR20","first-page":"1","volume-title":"Polytopes - Combinatorics and Computation, DMV Seminar","author":"G.M. Ziegler","year":"2000","unstructured":"Ziegler, G.M.: Lectures on 0\/1-polytopes. In: Kalai, G., Ziegler, G.M. (eds.) Polytopes - Combinatorics and Computation, DMV Seminar, vol.\u00a029, pp. 1\u201343. Birkh\u00e4user, Basel (2000)"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2010"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-15155-2_8.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T03:01:52Z","timestamp":1606186912000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-15155-2_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642151545","9783642151552"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-15155-2_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010]]}}}