{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T15:45:45Z","timestamp":1725551145648},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540294986"},{"type":"electronic","value":"9783540322450"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11571155_11","type":"book-chapter","created":{"date-parts":[[2005,10,31]],"date-time":"2005-10-31T07:32:31Z","timestamp":1130743951000},"page":"107-115","source":"Crossref","is-referenced-by-count":0,"title":["On Some Bounds on the Size of Branching Programs (A Survey)"],"prefix":"10.1007","author":[{"given":"Elizaveta A.","family":"Okol\u2019nishnikova","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"11_CR1","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1016\/0304-3975(90)90080-2","volume":"74","author":"L. Babai","year":"1990","unstructured":"Babai, L., Pudl\u00e1k, P., R\u00f6dl, V., Szemer\u00e9di, M.: Lower bounds to the complexity of symmetric Boolean functions. Theoretical Computer Science\u00a074, 313\u2013324 (1990)","journal-title":"Theoretical Computer Science"},{"key":"11_CR2","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1016\/S0890-5401(02)93174-3","volume":"178","author":"B. Bollig","year":"2002","unstructured":"Bollig, B., Sauerhoff, M., Wegener, I.: On the nonappoximability on boolean functions by OBDD and read-k-times branching programs. Information and Computation\u00a0178, 263\u2013278 (2002)","journal-title":"Information and Computation"},{"issue":"1","key":"11_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01200404","volume":"3","author":"A. Borodin","year":"1993","unstructured":"Borodin, A., Razborov, A., Smolensky, R.: On lower bounds for read-k-times branching programs. Computational Complexity\u00a03(1), 1\u201318 (1993)","journal-title":"Computational Complexity"},{"key":"11_CR4","volume-title":"The theory of Error-Correcting Codes","author":"F.J. MacWilliams","year":"1977","unstructured":"MacWilliams, F.J., Sloane, N.J.F.: The theory of Error-Correcting Codes. North-Holland, Amsterdam (1977)"},{"key":"11_CR5","first-page":"999","volume":"7","author":"E. Ne\u010diporuk","year":"1966","unstructured":"Ne\u010diporuk, E.: On a Boolean function. Soviet Math. Doklady\u00a07, 999\u20131000 (1966)","journal-title":"Soviet Math. Doklady"},{"key":"11_CR6","unstructured":"Okol\u2019nishnikova, E.A.: Lower bounds on complexity for the realization of characteristic functions of binary codes by binary programs. Metody Diskret. Anal.\u00a051, 61\u201383 (1991) (in Russian) (see also: Siberian Adv. Math., 3(1), 152\u2013166) (1993)"},{"key":"11_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"376","DOI":"10.1007\/BFb0036199","volume-title":"Fundamentals of Computation Theory","author":"E.A. Okol\u2019nishnikova","year":"1997","unstructured":"Okol\u2019nishnikova, E.A.: On the hierarchy of nondeterministic branching k-programs. In: Chlebus, B.S., Czaja, L. (eds.) FCT 1997. LNCS, vol.\u00a01279, pp. 376\u2013387. Springer, Heidelberg (1997)"},{"key":"11_CR8","unstructured":"Okol\u2019nishnikova, E.A.: On one method of obtaining of lower bounds of Boolean functions for nondeterministic branching programs. Diskretn. Anal. Issled. Oper. Ser. 1\u00a08(4), 76\u2013102 (2001) (in Russian) (see also: ECCC TR02-020,2002), available at \n                  \n                    http:\/\/www.eccc.uni-tri.de\/eccc\/\n                  \n                  \n                 (in English)"},{"issue":"3","key":"11_CR9","first-page":"67","volume":"10","author":"E.A. Okol\u2019nishnikova","year":"2003","unstructured":"Okol\u2019nishnikova, E.A.: On the complexity of nondeterministic branching programs for characteristic functions of Reed\u2013Muller codes. Diskretn. Anal. Issled. Oper. Ser. 1\u00a010(3), 67\u201381 (2003) (in Russian)","journal-title":"Diskretn. Anal. Issled. Oper. Ser. 1"},{"key":"11_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"480","DOI":"10.1007\/BFb0030331","volume-title":"Mathematical Foundations of Computer Science 1984","author":"P. Pudl\u00e1k","year":"1984","unstructured":"Pudl\u00e1k, P.: A lower bound on complexity of branching programs. In: Chytil, M.P., Koubek, V. (eds.) MFCS 1984. LNCS, vol.\u00a0176, pp. 480\u2013489. Springer, Heidelberg (1984)"},{"issue":"5","key":"11_CR11","first-page":"449","volume":"6","author":"P. Pudl\u00e1k","year":"1987","unstructured":"Pudl\u00e1k, P.: The hierarchy of Boolean circuits. Comput. Artificial Intelligence\u00a06(5), 449\u2013468 (1987)","journal-title":"Comput. Artificial Intelligence"},{"issue":"6","key":"11_CR12","first-page":"79","volume":"48","author":"A.A. Razborov","year":"1990","unstructured":"Razborov, A.A.: Lower bounds on the complexity of symmetric Boolean functions by switching-rectifier circuits. Matemat. zametki\u00a048(6), 79\u201390 (1990)","journal-title":"Matemat. zametki"},{"key":"11_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1007\/3-540-54458-5_49","volume-title":"Fundamentals of Computation Theory","author":"A.A. Razborov","year":"1991","unstructured":"Razborov, A.A.: Lower bounds for deterministic and nondeterministic branching program. In: Budach, L. (ed.) FCT 1991. LNCS, vol.\u00a0529, pp. 47\u201361. Springer, Heidelberg (1991)"},{"key":"11_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/BFb0028553","volume-title":"STACS 98","author":"M. Sauerhoff","year":"1998","unstructured":"Sauerhoff, M.: Randomness versus nondeterminism for read-once and read-k branching programs. In: Meinel, C., Morvan, M. (eds.) STACS 1998. LNCS, vol.\u00a01373, pp. 105\u2013115. Springer, Heidelberg (1998)"},{"key":"11_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1007\/3-540-36494-3_28","volume-title":"STACS 2003","author":"M. Sauerhoff","year":"2003","unstructured":"Sauerhoff, M.: Randomness versus nondeterminism for read-once and read-k branching programs. In: Alt, H., Habib, M. (eds.) STACS 2003. LNCS, vol.\u00a02607, pp. 307\u2013318. Springer, Heidelberg (2003)"},{"key":"11_CR16","doi-asserted-by":"crossref","unstructured":"Thathachar, J.S.: On separating the read-k-times program hierarchy. In: Proc. of the 30th annual ACM Symposium on theory of computing, pp. 652\u2013662 (1998)","DOI":"10.1145\/276698.276881"},{"issue":"5","key":"11_CR17","doi-asserted-by":"publisher","first-page":"1412","DOI":"10.1109\/18.133259","volume":"37","author":"V.K. Wei","year":"1991","unstructured":"Wei, V.K.: Generalized Hamming weights for linear codes. IEEE Trans. on Inform. Theory\u00a037(5), 1412\u20131418 (1991)","journal-title":"IEEE Trans. on Inform. Theory"}],"container-title":["Lecture Notes in Computer Science","Stochastic Algorithms: Foundations and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11571155_11.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T06:40:30Z","timestamp":1619505630000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11571155_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540294986","9783540322450"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/11571155_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}