{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T00:06:43Z","timestamp":1725667603823},"publisher-location":"Wiesbaden","reference-count":10,"publisher":"Vieweg+Teubner Verlag","isbn-type":[{"type":"print","value":"9783519026501"},{"type":"electronic","value":"9783322848239"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/978-3-322-84823-9_19","type":"book-chapter","created":{"date-parts":[[2012,3,10]],"date-time":"2012-03-10T04:25:18Z","timestamp":1331353518000},"page":"203-212","source":"Crossref","is-referenced-by-count":0,"title":["Komplexit\u00e4tstheoretische Ergebnisse f\u00fcr Randomisierte Branchingprogramme"],"prefix":"10.1007","author":[{"given":"Martin","family":"Sauerhoff","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"19_CR1","doi-asserted-by":"crossref","unstructured":"F. Ablayev. Randomization and nondeterminism are incomparable for polynomial ordered binary decision diagrams. In Proc. of 24th ICALP, LNCS 1256, 195\u2013202. Springer, 1997.","DOI":"10.1007\/3-540-63165-8_177"},{"key":"19_CR2","doi-asserted-by":"crossref","unstructured":"F. Ablayev und M. Karpinski. On the power of randomized branching programs. In Proc. of 23rd ICALP, LNCS 1099, 348\u2013356. Springer, 1996.","DOI":"10.1007\/3-540-61440-0_141"},{"issue":"6","key":"19_CR3","doi-asserted-by":"publisher","first-page":"2103","DOI":"10.1137\/S0097539797325636","volume":"28","author":"AE Andreev","year":"1999","unstructured":"A. E. Andreev, A. E. F. Clementi, J. D. P. Rolim und L. Trevisan. Weak random sources, hitting sets, and BPP simulations. SIAM J. Comp., 28(6):2103\u20132116, 1999.","journal-title":"SIAM J. Comp."},{"key":"19_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01200404","volume":"3","author":"A Borodin","year":"1993","unstructured":"A. Borodin, A. A. Razborov und R. Smolensky. On lower bounds for read-k-times branching programs. Computational Complexity, 3:1\u201318, 1993.","journal-title":"Computational Complexity"},{"key":"19_CR5","doi-asserted-by":"crossref","unstructured":"R. Impagliazzo und A. Wigderson. P = BPP if E requires exponential circuits: Derandomizing the XOR lemma. In Proc. of 29th STOC, 220\u2013228, 1997.","DOI":"10.1145\/258533.258590"},{"key":"19_CR6","doi-asserted-by":"crossref","unstructured":"S. Jukna, A. Razborov, P. Savick\u00fd und I. Wegener. On P versus NP \u2229 co-NP for decision trees and read-once branching programs. In Proc. of 22nd MFCS, LNCS 1295, 319\u2013326. Springer, 1997. Erscheint in Computational Complexity.","DOI":"10.1007\/BFb0029975"},{"issue":"1","key":"19_CR7","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/0020-0190(82)90139-9","volume":"14","author":"K-I Ko","year":"1982","unstructured":"K.-I. Ko. Some observations on the probabilistic algorithms and NP-hard problems. Information Processing Letters, 14(1):39\u201343, Mar. 1982.","journal-title":"Information Processing Letters"},{"key":"19_CR8","doi-asserted-by":"crossref","unstructured":"M. Sauerhoff. Lower bounds for randomized read-k-times branching programs. In Proc. of 15th STACS, LNCS 1373, 105\u2013115. Springer, 1998.","DOI":"10.1007\/BFb0028553"},{"key":"19_CR9","doi-asserted-by":"crossref","unstructured":"M. Sauerhoff. On the size of randomized OBDDs and read-once branching programs for k-stable functions. In Proc. of 16th STACS, LNCS 1563, 488\u2013499. Springer, 1999.","DOI":"10.1007\/3-540-49116-3_46"},{"key":"19_CR10","doi-asserted-by":"crossref","unstructured":"I. Wegener. Branching Programs and Binary Decision Diagrams\u2014Theory and Applications. Monographs on Discrete and Applied Mathematics. SIAM. Erscheint im Juli 2000.","DOI":"10.1137\/1.9780898719789"}],"container-title":["Ausgezeichnete Informatikdissertationen 1999"],"original-title":[],"language":"de","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-322-84823-9_19.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,2]],"date-time":"2021-05-02T13:41:03Z","timestamp":1619962863000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-322-84823-9_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783519026501","9783322848239"],"references-count":10,"URL":"https:\/\/doi.org\/10.1007\/978-3-322-84823-9_19","relation":{},"subject":[],"published":{"date-parts":[[2000]]}}}