{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T15:45:47Z","timestamp":1725551147930},"publisher-location":"Berlin, Heidelberg","reference-count":35,"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_16","type":"book-chapter","created":{"date-parts":[[2005,10,31]],"date-time":"2005-10-31T02:32:31Z","timestamp":1130725951000},"page":"190-201","source":"Crossref","is-referenced-by-count":0,"title":["The Complexity of Classical and Quantum Branching Programs: A Communication Complexity Approach"],"prefix":"10.1007","author":[{"given":"Farid","family":"Ablayev","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"16_CR1","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1016\/0304-3975(95)00157-3","volume":"157","author":"F. Ablayev","year":"1996","unstructured":"Ablayev, F.: Lower bounds for one-way probabilistic communication complexity and their application to space complexity. Theoretical Computer Science\u00a0157, 139\u2013159 (1996)","journal-title":"Theoretical Computer Science"},{"key":"16_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1007\/3-540-63165-8_177","volume-title":"Automata, Languages and Programming","author":"F. Ablayev","year":"1997","unstructured":"Ablayev, F.: Randomization and nondeterminism are incomparable for ordered-read once branching programs. In: Degano, P., Gorrieri, R., Marchetti-Spaccamela, A. (eds.) ICALP 1997. LNCS, vol.\u00a01256, pp. 195\u2013202. Springer, Heidelberg (1997)"},{"key":"16_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"348","DOI":"10.1007\/3-540-61440-0_141","volume-title":"Automata, Languages and Programming","author":"F. Ablayev","year":"1996","unstructured":"Ablayev, F., Karpinski, M.: On the power of randomized branching programs. In: Meyer auf der Heide, F., Monien, B. (eds.) ICALP 1996. LNCS, vol.\u00a01099, pp. 348\u2013356. Springer, Heidelberg (1996)"},{"key":"16_CR4","unstructured":"Ablayev, F., Karpinski, M.: On the Power of Randomized Ordered Branching Programs. Electronic Colloquium on Computational Complexity, TR98-004 (1998), available at http:\/\/www.eccc.uni-trier.de\/eccc\/"},{"issue":"1","key":"16_CR5","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1016\/S0890-5401(03)00118-4","volume":"186","author":"F. Ablayev","year":"2003","unstructured":"Ablayev, F., Karpinski, M.: A lower bound for integer multiplication on randomized ordered read-once branching programs. Information and Computation\u00a0186(1), 78\u201389 (2003)","journal-title":"Information and Computation"},{"key":"16_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1007\/3-540-44669-9_8","volume-title":"Fundamentals of Computation Theory","author":"F. Ablayev","year":"2001","unstructured":"Ablayev, F., Gainutdinova, A., Karpinski, M.: On the computational power of quantum branching programs. In: Freivalds, R. (ed.) FCT 2001. LNCS, vol.\u00a02138, pp. 59\u201370. Springer, Heidelberg (2001)"},{"key":"16_CR7","unstructured":"Agrawal, M., Thierauf, T.: The Satisfiability Problem for Probabilistic Ordered Branching Programs. Electronic Colloquium on Computational Complexity, TR97-060 (1997), available at http:\/\/www.eccc.uni-trier.de\/eccc\/"},{"key":"16_CR8","series-title":"Algorithms and Complexity","first-page":"757","volume-title":"Handbook of Theoretical Computer Science","author":"R. Boppana","year":"1990","unstructured":"Boppana, R., Sipser, M.: The complexity of finite functions. In: Van Leeuwen, J. (ed.) Handbook of Theoretical Computer Science. Algorithms and Complexity, vol.\u00a0A, pp. 757\u2013804. MIT Press, Elsevier, The Netherlands (1990)"},{"issue":"2","key":"16_CR9","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1109\/12.73590","volume":"40","author":"R. Bryant","year":"1991","unstructured":"Bryant, R.: On the complexity of VLSI implementations and graph representations of boolean functions with applications to integer multiplication. IEEE Trans. Comput.\u00a040(2), 205\u2013213 (1991)","journal-title":"IEEE Trans. Comput."},{"issue":"3","key":"16_CR10","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1145\/136035.136043","volume":"24","author":"R. Bryant","year":"1992","unstructured":"Bryant, R.: Symbolic boolean manipulation with ordered binary decision diagrams. ACM Computing Surveys\u00a024(3), 293\u2013318 (1992)","journal-title":"ACM Computing Surveys"},{"key":"16_CR11","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\u201318 (1993)","journal-title":"Computational Complexity"},{"key":"16_CR12","unstructured":"Bolling, B., Sauerhoff, M., Sieling, D., Wegener, I.: On the power of different types of restricted branching programs. ECCC Reports 1994, TR94-025 (1994), Available at http:\/\/www.eccc.uni-trier.de\/eccc\/"},{"key":"16_CR13","unstructured":"Jukna, S.: Complexity of Boolean Functions, see. Electronic Colloquium on Computational Complexity, section Lecture Notes, available at http:\/\/www.eccc.uni-trier.de\/eccc\/"},{"key":"16_CR14","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-03442-2","volume-title":"Communication complexity and parallel computations","author":"J. Hromkovic","year":"1997","unstructured":"Hromkovic, J.: Communication complexity and parallel computations. Springer, Heidelberg (1997)"},{"key":"16_CR15","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1007\/BF01206317","volume":"5","author":"M. Karchmer","year":"1995","unstructured":"Karchmer, M., Raz, R., Wigderson, A.: Super-logarithmic Depth Lower Bounds Via the Direct Sum in Communication Complexity. Computational Complexity\u00a05, 191\u2013204 (1995)","journal-title":"Computational Complexity"},{"key":"16_CR16","doi-asserted-by":"crossref","unstructured":"Klauck, H.: On quantum and probabilistic communication: La Vegas and one-way protocols. In: Proc. of the 32nd ACM Symp. Theory of Computing (2000)","DOI":"10.1145\/335305.335396"},{"key":"16_CR17","doi-asserted-by":"crossref","unstructured":"Kremer, I., Nisan, N., Ron, D.: On randomized one-round communication complexity. In: Proceedings of the 27th annual ACM symposium on Theory of computing, pp. 596\u2013605 (1995)","DOI":"10.1145\/225058.225277"},{"key":"16_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1007\/BFb0017163","volume-title":"Mathematical Foundations of Computer Science 1988","author":"M. Krause","year":"1988","unstructured":"Krause, M., Meinel, C., Waack, S.: Separating the eraser Turing machine classes L e , NL e , co\u2009\u2212\u2009NL e , and P e . In: Koubek, V., Janiga, L., Chytil, M.P. (eds.) MFCS 1988. LNCS, vol.\u00a0324, pp. 405\u2013413. Springer, Heidelberg (1988)"},{"key":"16_CR19","volume-title":"Communication comple xity","author":"E. Kushilevitz","year":"1997","unstructured":"Kushilevitz, E., Nisan, N.: Communication comple xity. Cambridge University Press, Cambridge (1997)"},{"key":"16_CR20","unstructured":"Meinel, C., Theobald, T.: Ordered Binary Decision Diagrams and Their Significance in Computer-Aided Design of VLSI Circuits - a Survey, Electronic Colloquium on Computational Complexity, TR98-039, available at http:\/\/www.eccc.uni-trier.de\/eccc"},{"key":"16_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"467","DOI":"10.1007\/3-540-44968-X_46","volume-title":"Computing and Combinatorics","author":"M. Nakanishi","year":"2000","unstructured":"Nakanishi, M., Hamaguchi, K., Kashiwabara, T.: Ordered quantum branching programs are more powerful than ordered probabilistic branching programs under a bounded-width restriction. In: Du, D.-Z., Eades, P., Sharma, A.K., Lin, X., Estivill-Castro, V. (eds.) COCOON 2000. LNCS, vol.\u00a01858, pp. 467\u2013476. Springer, Heidelberg (2000)"},{"key":"16_CR22","volume-title":"Quantum Computation and Quantum Information","author":"M.A. Nielsen","year":"2000","unstructured":"Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge (2000)"},{"key":"16_CR23","unstructured":"Oklonishnikova, E.: On one lower bound for branching programs. Electronic Colloquium on Computational Complexity, TR02-020, available at http:\/\/www.eccc.uni-trier.de\/eccc"},{"key":"16_CR24","doi-asserted-by":"crossref","unstructured":"Ponzio, S.: A lower bound for integer multiplication with read-once branching programs. In: Proceedings of the 27-th STOC, pp. 130\u2013139 (1995)","DOI":"10.1145\/225058.225098"},{"key":"16_CR25","unstructured":"Ponzio, S.: Restricted Branching Programs and Hardware Verification, PhD Theses, Massachusetts Institute of Technology (1995), Available at http:\/\/www.eccc.uni-trier.de\/eccc"},{"key":"16_CR26","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. Razborov","year":"1991","unstructured":"Razborov, A.: Lower bounds for deterministic and nondeterministic branching programs. In: Budach, L. (ed.) FCT 1991. LNCS, vol.\u00a0529, pp. 47\u201360. Springer, Heidelberg (1991)"},{"key":"16_CR27","doi-asserted-by":"crossref","unstructured":"Raz, R., McKenzie, P.: Separation of the monotone NC hierarchy. In: Proc. of the 38th Annual Symposium on Foundation of Computer Science, pp. 234\u2013243 (1997)","DOI":"10.1109\/SFCS.1997.646112"},{"key":"16_CR28","unstructured":"Sauerhoff, M.: A lower bounds for randomized read-k-times branching programs Electronic Colloquium on Computational Complexity, TR97-019 (1997), available at http:\/\/www.eccc.uni-trier.de\/eccc\/"},{"key":"16_CR29","unstructured":"Savicky, P., Zak, S.: A large lower bound for 1-branching programs, Electronic Colloquium on Computational Complexity, Revision 01 of TR96-036 (1996), available at http:\/\/www.eccc.uni-trier.de\/eccc\/"},{"key":"16_CR30","unstructured":"Savicky, P., Zak, S.: A hierarchy for (1, + k)-branching programs with respect to k, Electronic Colloquium on Computational Complexity, TR96-050 (1996), available at http:\/\/www.eccc.uni-trier.de\/eccc\/"},{"key":"16_CR31","doi-asserted-by":"crossref","unstructured":"Simon, J., Szegedy, M.: A new lower bound theorem for read-only-once branching programs and its applications. In: Cai, J.-Y. (ed.) Advances in Computational Complexity Theory. DIMACS Series, vol.\u00a013, pp. 183\u2013193. AMS (1993)","DOI":"10.1090\/dimacs\/013\/11"},{"key":"16_CR32","unstructured":"Sauerhoff, M., Sieling, D.: Quantum branching programs and space-bounded nonuniform quantum complexity. ph\/0403164 (March 2004)"},{"key":"16_CR33","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1016\/0012-365X(95)90790-R","volume":"136","author":"I. Wegener","year":"1994","unstructured":"Wegener, I.: Efficient data structures for boolean functions. Discrete Mathematics\u00a0136, 347\u2013372 (1994)","journal-title":"Discrete Mathematics"},{"key":"16_CR34","doi-asserted-by":"crossref","unstructured":"Wegener, I.: Branching Programs and Binary Decision Diagrams. SIAM Monographs on Discrete Mathematics and Applications (2000)","DOI":"10.1137\/1.9780898719789"},{"key":"16_CR35","doi-asserted-by":"crossref","unstructured":"Yao, A.: Some Complexity Questions Related to Distributive Computing. In: Proceedings of the 11th Annual ACM Symposium on the Theory of Computing, pp. 209\u2013213 (1979)","DOI":"10.1145\/800135.804414"}],"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_16.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T14:55:34Z","timestamp":1605624934000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11571155_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540294986","9783540322450"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/11571155_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}