{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:54:05Z","timestamp":1725663245420},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540514985"},{"type":"electronic","value":"9783540481805"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1989]]},"DOI":"10.1007\/3-540-51498-8_12","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T21:00:44Z","timestamp":1330203644000},"page":"127-136","source":"Crossref","is-referenced-by-count":7,"title":["Separating completely complexity classes related to polynomial size \u03a9-Decision trees"],"prefix":"10.1007","author":[{"given":"Carsten","family":"Damm","sequence":"first","affiliation":[]},{"given":"Christoph","family":"Meinel","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,28]]},"reference":[{"key":"12_CR1","doi-asserted-by":"crossref","unstructured":"M.Ajtai, L.Babai, P.Hajnal, J.Komlos, P.Pudlak, V.Rdl, E.Szemeredi, G.Tur\u00e1n: Two lower bounds for branching programs, Proc. 18th ACM STOC, 30\u201338.","DOI":"10.1145\/12130.12134"},{"key":"12_CR2","unstructured":"A.E. Andreev: On a method of obtaining lower bounds for the complexity of individual monotone functions, Dokl. Akad. Nauk SSSR 282\/5, 1033\u20131037."},{"key":"12_CR3","first-page":"221","volume":"21","author":"L. Budach","year":"1985","unstructured":"L. Budach: A lower bound for the number of nodes in a decision tree. EIK 21 (1985), 221\u2013228.","journal-title":"EIK"},{"key":"12_CR4","doi-asserted-by":"crossref","unstructured":"Furst, Saxe, M. Sipser: Parity, circuits and the polynomial time hierarchy, Proc. 22th IEEE FOCS, 1981, 260\u2013270.","DOI":"10.1109\/SFCS.1981.35"},{"key":"12_CR5","doi-asserted-by":"crossref","unstructured":"J.Hastad: Improved lower bounds for small depth circuits, Proc. 18th ACM STOC (1986), 6\u201320.","DOI":"10.1145\/12130.12132"},{"key":"12_CR6","doi-asserted-by":"crossref","unstructured":"M.Krause, Ch.Meinel, S.Waack: Separating the eraser Turing machine classes L, NL, co-NL and P, Proc. MFCS'88, LNCS 324, 405\u2013413.","DOI":"10.1007\/BFb0017163"},{"key":"12_CR7","doi-asserted-by":"crossref","unstructured":"Ch.Meinel: The power of polynomial size \u03a9-branching programs, Proc. STACS'88 Bordeaux, LNCS 294, 81\u201390.","DOI":"10.1007\/BFb0035834"},{"key":"12_CR8","unstructured":"M.S.Paterson: On Razborov's result for bounded depth circuits over {\u2295, \u039b}, manuscript."},{"key":"12_CR9","first-page":"6","volume":"37","author":"A.A.Razborov","year":"1985","unstructured":"A.A.Razborov: A lower bound for the monotone network complexity of the logical permanent, Matem. Zametki 37\/6 (1985).","journal-title":"Matem. Zametki"},{"key":"12_CR10","doi-asserted-by":"crossref","unstructured":"A.A.Razborov: Lower bounds on the size of circuits of bounded depth over the basis {\u039b, \u2295}, preprint, Steklov Inst. for Math., Moscow 1986, (see also Mat. Zam. 41, no.4 (1987), 598\u2013607) (in Russian).","DOI":"10.1070\/RM1986v041n04ABEH003385"},{"issue":"2\/3","key":"12_CR11","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/S0019-9958(84)80031-5","volume":"62","author":"I. Wegener","year":"1984","unstructured":"I. Wegener: Optimal decision trees and one-time-only branching programs for symmetric Boolean functions, Inf. and Control, Vol. 62, Nos. 2\/3 (1984), 129\u2013143.","journal-title":"Inf. and Control"},{"issue":"2","key":"12_CR12","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1145\/42282.46161","volume":"35","author":"I. Wegener","year":"1988","unstructured":"I. Wegener: On the Complexity of Branching Programs and Decision Trees for Clique Functions, JACM Vol. 35, No. 2 (1988), 461\u2013471.","journal-title":"JACM"},{"key":"12_CR13","doi-asserted-by":"crossref","unstructured":"A.C.Yao Separating the polynomial-time hierarchy by oracles, Proc.26th IEEE FOCS (1985), 1\u201310.","DOI":"10.1109\/SFCS.1985.49"}],"container-title":["Lecture Notes in Computer Science","Fundamentals of Computation Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-51498-8_12.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:21:33Z","timestamp":1605648093000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-51498-8_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989]]},"ISBN":["9783540514985","9783540481805"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/3-540-51498-8_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1989]]}}}