{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:38:00Z","timestamp":1759639080596},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662460771"},{"type":"electronic","value":"9783662460788"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-46078-8_34","type":"book-chapter","created":{"date-parts":[[2015,1,14]],"date-time":"2015-01-14T09:54:29Z","timestamp":1421229269000},"page":"412-422","source":"Crossref","is-referenced-by-count":0,"title":["Lower Bounds for Linear Decision Trees with Bounded Weights"],"prefix":"10.1007","author":[{"given":"Kei","family":"Uchizawa","sequence":"first","affiliation":[]},{"given":"Eiji","family":"Takimoto","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"2","key":"34_CR1","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1006\/jcss.1995.1017","volume":"50","author":"R. Beigel","year":"1995","unstructured":"Beigel, R., Reingold, N., Spielman, D.: PP is closed under intersection. Journal of Computer and System Sciences\u00a050(2), 191\u2013202 (1995)","journal-title":"Journal of Computer and System Sciences"},{"issue":"4","key":"34_CR2","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1016\/0020-0190(92)90237-P","volume":"42","author":"A. Blum","year":"1992","unstructured":"Blum, A.: Rank-r decision trees are a subclass of r-decision lists. Information Processing Letters\u00a042(4), 183\u2013185 (1992)","journal-title":"Information Processing Letters"},{"key":"34_CR3","first-page":"1","volume":"3","author":"D.P. Dobkin","year":"1982","unstructured":"Dobkin, D.P., Lipton, R.J.: On the complexity of computations under varying sets of primitives. Journal of Computer and System Sciences\u00a03, 1\u20138 (1982)","journal-title":"Journal of Computer and System Sciences"},{"issue":"3","key":"34_CR4","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/0890-5401(89)90001-1","volume":"82","author":"A. Ehrenfeucht","year":"1989","unstructured":"Ehrenfeucht, A., Haussler, D.: Learning decision trees from random examples. Information and Computation\u00a082(3), 231\u2013246 (1989)","journal-title":"Information and Computation"},{"key":"34_CR5","unstructured":"Erickson, J.: Lower bounds for linear satisfiability problems. In: Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 388\u2013395 (1995)"},{"key":"34_CR6","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1006\/inco.1999.2788","volume":"152","author":"R. Fleischer","year":"1999","unstructured":"Fleischer, R.: Decision trees: Old and new results. Information and Computation\u00a0152, 44\u201361 (1999)","journal-title":"Information and Computation"},{"key":"34_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1007\/3-540-45294-X_15","volume-title":"FST TCS 2001: Foundations of Software Technology and Theoretical Computer Science","author":"J. Forster","year":"2001","unstructured":"Forster, J., Krause, M., Lokam, S.V., Mubarakzjanov, R., Schmitt, N., Simon, H.U.: Relations between communication complexity, linear arrangements, and computational complexity. In: Hariharan, R., Mukund, M., Vinay, V. (eds.) FSTTCS 2001. LNCS, vol.\u00a02245, pp. 171\u2013182. Springer, Heidelberg (2001)"},{"key":"34_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"707","DOI":"10.1007\/3-540-54233-7_176","volume-title":"Automata, Languages and Programming","author":"H.D. Gr\u00f6ger","year":"1991","unstructured":"Gr\u00f6ger, H.D., Tur\u00e1n, G.: On linear decision trees computing boolean functions. In: Leach Albert, J., Monien, B., Rodr\u00edguez-Artalejo, M. (eds.) ICALP 1991. LNCS, vol.\u00a0510, pp. 707\u2013718. Springer, Heidelberg (1991)"},{"key":"34_CR9","doi-asserted-by":"crossref","unstructured":"H\u00e5stad, J.: On the size of weights for threshold gates. SIAM Journal on Discrete Mathematics, 484\u2013492 (1994)","DOI":"10.1137\/S0895480192235878"},{"key":"34_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"136","DOI":"10.1007\/3-540-61332-3_146","volume-title":"Computing and Combinatorics","author":"T. Hofmeister","year":"1996","unstructured":"Hofmeister, T.: A Note on the Simulation of Exponential Threshold Weights. In: Cai, J.-Y., Wong, C.K. (eds.) COCOON 1996. LNCS, vol.\u00a01090, pp. 136\u2013141. Springer, Heidelberg (1996)"},{"issue":"2","key":"34_CR11","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1016\/j.jcss.2003.07.007","volume":"68","author":"A.R. Klivans","year":"2004","unstructured":"Klivans, A.R., Servedio, R.A.: Learning DNF in time \n                      \n                        \n                      \n                      $2^{n^{1\/3}poly(\\log n)}$\n                    . Journal of Computer and System Sciences\u00a068(2), 303\u2013318 (2004)","journal-title":"Journal of Computer and System Sciences"},{"key":"34_CR12","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":"34_CR13","volume-title":"Discrete Neural Computation; A Theoretical Foundation","author":"K.Y. Siu","year":"1995","unstructured":"Siu, K.Y., Roychowdhury, V., Kailath, T.: Discrete Neural Computation; A Theoretical Foundation. Prentice-Hall, Inc., Upper Saddle River (1995)"},{"key":"34_CR14","first-page":"86","volume":"18","author":"J.M. Steele","year":"1979","unstructured":"Steele, J.M., Yao, A.C.: Lower bounds for algebraic decision trees. Journal of Algorithms\u00a018, 86\u201391 (1979)","journal-title":"Journal of Algorithms"},{"key":"34_CR15","unstructured":"Nisan, N.: The communication complexity of threshold gates. In: Proceedings of \u201cCombinatorics, Paul Erd\u00f6s is Eighty\u201d, pp. 301\u2013315 (1999)"},{"issue":"2","key":"34_CR16","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1016\/j.jcss.2003.07.007","volume":"68","author":"A.R. Klivans","year":"2004","unstructured":"Klivans, A.R., Servedio, R.A.: Learning DNF in time \n                      \n                        \n                      \n                      $2^{\\tilde{O}(n^{1\/3})}$\n                    . Journal of Computer and System Sciences\u00a068(2), 303\u2013318 (2004)","journal-title":"Journal of Computer and System Sciences"},{"key":"34_CR17","doi-asserted-by":"crossref","unstructured":"Tur\u00e1n, G., Vatan, F.: Linear decision lists and partitioning algorithms for the construction of neural networks. Foundations of Computational Mathematics, 414\u2013423 (1997)","DOI":"10.1007\/978-3-642-60539-0_34"},{"key":"34_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"568","DOI":"10.1007\/978-3-642-22993-0_51","volume-title":"Mathematical Foundations of Computer Science 2011","author":"K. Uchizawa","year":"2011","unstructured":"Uchizawa, K., Takimoto, E.: Lower Bounds for Linear Decision Trees via an Energy Complexity Argument. In: Murlak, F., Sankowski, P. (eds.) MFCS 2011. LNCS, vol.\u00a06907, pp. 568\u2013579. Springer, Heidelberg (2011)"}],"container-title":["Lecture Notes in Computer Science","SOFSEM 2015: Theory and Practice of Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-46078-8_34","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,28]],"date-time":"2019-05-28T23:58:41Z","timestamp":1559087921000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-46078-8_34"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662460771","9783662460788"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-46078-8_34","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]}}}