{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,10]],"date-time":"2026-02-10T19:16:03Z","timestamp":1770750963366,"version":"3.50.0"},"publisher-location":"Berlin, Heidelberg","reference-count":40,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540542339","type":"print"},{"value":"9783540475163","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1991]]},"DOI":"10.1007\/3-540-54233-7_176","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T22:39:33Z","timestamp":1330209573000},"page":"707-718","source":"Crossref","is-referenced-by-count":15,"title":["On linear decision trees computing Boolean functions"],"prefix":"10.1007","author":[{"given":"Hans Dietmar","family":"Gr\u00f6ger","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gy\u00f6rgy","family":"Tur\u00e1n","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,8]]},"reference":[{"key":"56_CR1","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1016\/0020-0190(89)90214-7","volume":"30","author":"A. Aggarwal","year":"1989","unstructured":"A. Aggarwal, D. Coppersmith, D. Kleitman (1989): A generalized model for understanding evasiveness, Inf. Proc. Lett.30, 205\u2013208.","journal-title":"Inf. Proc. Lett."},{"key":"56_CR2","unstructured":"L. Babai, P. Frankl, J. Simon (1986): Complexity classes in communication complexity, 27.FOCS, 337\u2013347."},{"key":"56_CR3","unstructured":"L. Babai, N. Nisan, M. Szegedy (1989): Multiparty protocols and logspace hard pseudorandom sequences, 21.STOC, 1\u201311."},{"key":"56_CR4","first-page":"150","volume":"38","author":"D. A. Barrington","year":"1989","unstructured":"D. A. Barrington (1989): Bounded-width polynomial size branching programs recognize exactly those languages in NC1, JCSS38, 150\u2013164.","journal-title":"JCSS"},{"key":"56_CR5","unstructured":"B. Bollob\u00e1s (1984): Extremal Graph Theory, Academic Press."},{"key":"56_CR6","unstructured":"L. Breiman, J.H. Friedman, R.A. Olshen, C.J. Stone (1984): Classification and regression trees, Wadsworth."},{"key":"56_CR7","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1137\/0403015","volume":"3","author":"J. Bruck","year":"1990","unstructured":"J. Bruck (1990): Harmonic analysis of polynomial threshold functions, SIAM J. Disc. Math.3, 168\u2013177.","journal-title":"SIAM J. Disc. Math."},{"key":"56_CR8","unstructured":"B. Chor, O. Goldreich (1985): Unbiased bits from sources of weak randomness and probabilistic communication complexity, 26.FOCS, 429\u2013442."},{"key":"56_CR9","unstructured":"M. Dietzfelbinger (1987), unpublished."},{"key":"56_CR10","first-page":"313","volume":"36","author":"M. Dietzfelbinger","year":"1988","unstructured":"M. Dietzfelbinger, W. Maass (1988): Lower bound arguments with \u201cinaccessible\u201d numbers, JCSS36, 313\u2013335.","journal-title":"JCSS"},{"key":"56_CR11","first-page":"413","volume":"16","author":"D.P. Dobkin","year":"1978","unstructured":"D.P. Dobkin, R.J. Lipton (1978): A lower bound of n2\/2 on linear search programs for the knapsack problem, JCSS16, 413\u2013417.","journal-title":"JCSS"},{"key":"56_CR12","first-page":"86","volume":"18","author":"D.P. Dobkin","year":"1979","unstructured":"D.P. Dobkin, R.J. Lipton (1979): On the complexity of computations under varying sets of primitives, JCSS18, 86\u201391.","journal-title":"JCSS"},{"key":"56_CR13","unstructured":"H.D. Gr\u00f6ger (1988), unpublished."},{"key":"56_CR14","unstructured":"H.D. Gr\u00f6ger (1989): On the randomized complexity of monotone graph properties, submitted."},{"key":"56_CR15","unstructured":"H.D. Gr\u00f6ger, Gy. Tur\u00e1n (1990): A linear lower bound for the size of threshold circuits, submitted."},{"key":"56_CR16","unstructured":"A. Hajnal, W. Maass, P. Pudl\u00e1k, M. Szegedy, Gy. Tur\u00e1n (1987): Threshold circuits of bounded depth, 28.FOCS, 99\u2013110."},{"key":"56_CR17","unstructured":"A. Hajnal, W. Maass, Gy. Tur\u00e1n (1988): On the communication complexity of graph properties, 20.STOC, 186\u2013191."},{"key":"56_CR18","unstructured":"P. Hajnal (1988): The complexity of graph problems, Ph.D. Thesis, University of Chicago, TR 88\u201313."},{"key":"56_CR19","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1007\/BF02579140","volume":"4","author":"J. Kahn","year":"1984","unstructured":"J. Kahn, M. Saks, D. Sturtevant (1984): A topological approach to evasiveness, Combinatorica4, 297\u2013306.","journal-title":"Combinatorica"},{"key":"56_CR20","unstructured":"V. King (1988): Lower bounds on the complexity of graph properties, 20.STOC, 468\u2013476."},{"key":"56_CR21","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1007\/BF00290735","volume":"19","author":"P. Klein","year":"1983","unstructured":"P. Klein, F. Meyer auf der Heide (1983): A lower time bound for the knapsack problem on random access machines, Acta Inf.19, 385\u2013395.","journal-title":"Acta Inf."},{"key":"56_CR22","doi-asserted-by":"crossref","first-page":"720","DOI":"10.1145\/3828.3838","volume":"31","author":"U. Manber","year":"1985","unstructured":"U. Manber, M. Tompa (1985): The complexity of problems on probabilistic, nondeterministic and alternating decision trees, JACM31, 720\u2013732.","journal-title":"JACM"},{"key":"56_CR23","doi-asserted-by":"crossref","first-page":"668","DOI":"10.1145\/828.322450","volume":"31","author":"F. Meyer auf der Heide","year":"1984","unstructured":"F. Meyer auf der Heide (1984): A polynomial linear search algorithm for the n-dimensional knapsack problem, JACM31, 668\u2013676.","journal-title":"JACM"},{"key":"56_CR24","doi-asserted-by":"crossref","first-page":"929","DOI":"10.1145\/4221.4250","volume":"32","author":"F. Meyer auf der Heide","year":"1985","unstructured":"F. Meyer auf der Heide (1985a): Lower bounds for solving linear diophantine equations on random access machines, JACM32, 929\u2013937.","journal-title":"JACM"},{"key":"56_CR25","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1016\/0304-3975(85)90079-9","volume":"41","author":"F. Meyer auf der Heide","year":"1985","unstructured":"F. Meyer auf der Heide (1985b): Simulating probabilistic by deterministic algebraic computation trees, TCS41, 325\u2013330.","journal-title":"TCS"},{"key":"56_CR26","doi-asserted-by":"crossref","unstructured":"F. Meyer auf der Heide (1985c): Nondeterministic versus probabilistic linear search algorithms, 26.FOCS, 65\u201373.","DOI":"10.1109\/SFCS.1985.38"},{"key":"56_CR27","unstructured":"N. Nisan: CREW PRAMs and decision trees (1989), 21.STOC, 327\u2013335."},{"key":"56_CR28","unstructured":"P. Pudl\u00e1k (1986), personal communication."},{"key":"56_CR29","first-page":"81","volume":"1","author":"J.R. Quinlan","year":"1986","unstructured":"J.R. Quinlan (1986): Induction of decision trees, Machine Learning1, 81\u2013106.","journal-title":"Machine Learning"},{"key":"56_CR30","doi-asserted-by":"crossref","unstructured":"D.E. Rumelhart, J.L. McClelland (1986): Parallel distributed processing: explorations in the microstructure of cognition, MIT Press.","DOI":"10.7551\/mitpress\/5236.001.0001"},{"key":"56_CR31","unstructured":"M. Saks, A. Wigderson (1986): Probabilistic Boolean decision trees and the complexity of evaluating game trees, 27.FOCS, 29\u201338."},{"key":"56_CR32","first-page":"305","volume":"115","author":"M. Snir","year":"1981","unstructured":"M. Snir: Proving lower bounds for linear decision trees (1981), 8.ICALP, LNCS115, 305\u2013315.","journal-title":"ICALP, LNCS"},{"key":"56_CR33","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1016\/0304-3975(82)90041-X","volume":"19","author":"M. Snir","year":"1982","unstructured":"M. Snir: Comparisons between linear functions can help (1982), TCS19, 321\u2013330.","journal-title":"TCS"},{"key":"56_CR34","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1016\/0304-3975(85)90210-5","volume":"38","author":"M. Snir","year":"1985","unstructured":"M. Snir (1985): Lower bounds on probabilistic linear decision trees, TCS38, 69\u201382.","journal-title":"TCS"},{"key":"56_CR35","first-page":"203","volume":"10","author":"T.G. Tarj\u00e1n","year":"1975","unstructured":"T.G. Tarj\u00e1n (1975): Complexity of lattice-configurations, Studia Sci. Math. Hung.10, 203\u2013211.","journal-title":"Studia Sci. Math. Hung."},{"key":"56_CR36","unstructured":"A.C. Yao (1975): On the complexity of comparison problems using linear functions, 16.FOCS, 85\u201389."},{"key":"56_CR37","doi-asserted-by":"crossref","unstructured":"A.C. Yao (1977): Probabilistic computations: toward a unified measure of complexity, 18.FOCS, 222\u2013227.","DOI":"10.1109\/SFCS.1977.24"},{"key":"56_CR38","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1016\/0304-3975(82)90060-3","volume":"19","author":"A.C. Yao","year":"1982","unstructured":"A.C. Yao (1982): On the time-space tradeoff for sorting with linear queries, TCS19, 203\u2013218.","journal-title":"TCS"},{"key":"56_CR39","first-page":"393","volume":"28","author":"A.C. Yao","year":"1987","unstructured":"A.C. Yao (1987): Lower bounds to randomized algorithms for graph properties, 28.FOCS, 393\u2013400.","journal-title":"FOCS"},{"key":"56_CR40","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1137\/0209028","volume":"9","author":"A.C. Yao","year":"1980","unstructured":"A.C. Yao, R. Rivest (1980): On the polyhedral decision problem, SIAM J. Comp.9, 343\u2013347.","journal-title":"SIAM J. Comp."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-54233-7_176.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T21:16:52Z","timestamp":1742591812000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-54233-7_176"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991]]},"ISBN":["9783540542339","9783540475163"],"references-count":40,"URL":"https:\/\/doi.org\/10.1007\/3-540-54233-7_176","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1991]]}}}