{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T07:36:58Z","timestamp":1774597018576,"version":"3.50.1"},"publisher-location":"Cham","reference-count":37,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319731162","type":"print"},{"value":"9783319731179","type":"electronic"}],"license":[{"start":{"date-parts":[[2017,12,22]],"date-time":"2017-12-22T00:00:00Z","timestamp":1513900800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-73117-9_14","type":"book-chapter","created":{"date-parts":[[2017,12,21]],"date-time":"2017-12-21T16:45:34Z","timestamp":1513874734000},"page":"197-211","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Lower Bounds and Hierarchies for Quantum Memoryless Communication Protocols and Quantum Ordered Binary Decision Diagrams with Repeated Test"],"prefix":"10.1007","author":[{"given":"Farid","family":"Ablayev","sequence":"first","affiliation":[]},{"given":"Andris","family":"Ambainis","sequence":"additional","affiliation":[]},{"given":"Kamil","family":"Khadiev","sequence":"additional","affiliation":[]},{"given":"Aliya","family":"Khadieva","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,12,22]]},"reference":[{"issue":"6","key":"14_CR1","doi-asserted-by":"crossref","first-page":"670","DOI":"10.1134\/S199508021606007X","volume":"37","author":"F Ablayev","year":"2016","unstructured":"Ablayev, F., Gainutdinova, A., Khadiev, K., Yakary\u0131lmaz, A.: Very narrow quantum OBDDs and width hierarchies for classical OBDDs. Lobachevskii J. Math. 37(6), 670\u2013682 (2016)","journal-title":"Lobachevskii J. Math."},{"key":"14_CR2","doi-asserted-by":"crossref","unstructured":"Ablayev, F., Ambainis, A., Khadiev, K., Khadieva, A.: Lower bounds and hierarchies for quantum memoryless communication protocols and quantum ordered binary decision diagrams with repeated test. arXiv preprint arXiv:1703.05015 (2017)","DOI":"10.1007\/978-3-319-73117-9_14"},{"key":"14_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1007\/11505877_7","volume-title":"Developments in Language Theory","author":"F Ablayev","year":"2005","unstructured":"Ablayev, F., Gainutdinova, A.: Complexity of quantum uniform and nonuniform automata. In: De Felice, C., Restivo, A. (eds.) DLT 2005. LNCS, vol. 3572, pp. 78\u201387. Springer, Heidelberg (2005). https:\/\/doi.org\/10.1007\/11505877_7"},{"key":"14_CR4","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 computational power of quantum branching programs. In: Freivalds, R. (ed.) FCT 2001. LNCS, vol. 2138, pp. 59\u201370. Springer, Heidelberg (2001). https:\/\/doi.org\/10.1007\/3-540-44669-9_8"},{"issue":"2","key":"14_CR5","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1016\/j.ic.2005.04.003","volume":"203","author":"F Ablayev","year":"2005","unstructured":"Ablayev, F., Gainutdinova, A., Karpinski, M., Moore, C., Pollett, C.: On the computational power of probabilistic and quantum branching program. Inf. Comput. 203(2), 145\u2013162 (2005)","journal-title":"Inf. Comput."},{"key":"14_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1007\/978-3-319-09704-6_6","volume-title":"Descriptional Complexity of Formal Systems","author":"F Ablayev","year":"2014","unstructured":"Ablayev, F., Gainutdinova, A., Khadiev, K., Yakary\u0131lmaz, A.: Very narrow quantum OBDDs and width hierarchies for classical OBDDs. In: J\u00fcrgensen, H., Karhum\u00e4ki, J., Okhotin, A. (eds.) DCFS 2014. LNCS, vol. 8614, pp. 53\u201364. Springer, Cham (2014). https:\/\/doi.org\/10.1007\/978-3-319-09704-6_6"},{"issue":"3","key":"14_CR7","doi-asserted-by":"crossref","first-page":"46","DOI":"10.3103\/S1066369X13030067","volume":"53","author":"F Ablayev","year":"2013","unstructured":"Ablayev, F., Khadiev, K.: Extension of the hierarchy for k-OBDDs of small width. Russ. Math. 53(3), 46\u201350 (2013)","journal-title":"Russ. Math."},{"key":"14_CR8","unstructured":"Ablayev, F., Khasianov, A., Vasiliev, A.: On complexity of quantum branching programs computing equality-like boolean functions. In: ECCC (2008, to appear in 2010)"},{"key":"14_CR9","doi-asserted-by":"crossref","unstructured":"Ambainis, A.: A new protocol and lower bounds for quantum coin flipping. In: Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing, pp. 134\u2013142. ACM (2001)","DOI":"10.1145\/380752.380788"},{"issue":"1","key":"14_CR10","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1016\/S0304-3975(02)00138-X","volume":"287","author":"A Ambainis","year":"2002","unstructured":"Ambainis, A., Watrous, J.: Two-way finite automata with quantum and classical states. Theoret. Comput. Sci. 287(1), 299\u2013311 (2002)","journal-title":"Theoret. Comput. Sci."},{"issue":"1","key":"14_CR11","doi-asserted-by":"crossref","first-page":"150","DOI":"10.1016\/0022-0000(89)90037-8","volume":"38","author":"DAM Barrington","year":"1989","unstructured":"Barrington, D.A.M.: Bounded-width polynomial-size branching programs recognize exactly those languages in NC $$^1$$ 1 . J. Comput. Syst. Sci. 38(1), 150\u2013164 (1989)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"14_CR12","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1016\/S0304-3975(97)00034-0","volume":"205","author":"B Bollig","year":"1998","unstructured":"Bollig, B., Sauerhoff, M., Sieling, D., Wegener, I.: Hierarchy theorems for kOBDDs and kIBDDs. Theoret. Comput. Sci. 205(1), 45\u201360 (1998)","journal-title":"Theoret. Comput. Sci."},{"key":"14_CR13","unstructured":"Chailloux, A., Kerenidis, I., Lauri\u00e8re, M.: The information cost of quantum memoryless protocols. arXiv preprint arXiv:1703.01061 (2017)"},{"issue":"11","key":"14_CR14","doi-asserted-by":"crossref","first-page":"26","DOI":"10.3103\/S1066369X15110031","volume":"59","author":"AF Gainutdinova","year":"2015","unstructured":"Gainutdinova, A.F.: Comparative complexity of quantum and classical OBDDs for total and partial functions. Russ. Math. 59(11), 26\u201335 (2015)","journal-title":"Russ. Math."},{"key":"14_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1007\/978-3-319-58747-9_13","volume-title":"Computer Science \u2013 Theory and Applications","author":"A Gainutdinova","year":"2017","unstructured":"Gainutdinova, A., Yakary\u0131lmaz, A.: Nondeterministic unitary OBDDs. In: Weil, P. (ed.) CSR 2017. LNCS, vol. 10304, pp. 126\u2013140. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-58747-9_13 . arXiv:1612.07015"},{"key":"14_CR16","unstructured":"Homeister, M., Waack, S.: Quantum ordered binary decision diagrams with repeated tests. arXiv preprint arXiv:quant-ph\/0507258 (2005)"},{"issue":"2","key":"14_CR17","doi-asserted-by":"crossref","first-page":"178","DOI":"10.1134\/S1995080215020092","volume":"36","author":"K Khadiev","year":"2015","unstructured":"Khadiev, K.: Width hierarchy for k-OBDD of small width. Lobachevskii J. Math. 36(2), 178\u2013183 (2015)","journal-title":"Lobachevskii J. Math."},{"issue":"6","key":"14_CR18","doi-asserted-by":"crossref","first-page":"682","DOI":"10.1134\/S1995080216060159","volume":"37","author":"K Khadiev","year":"2016","unstructured":"Khadiev, K.: On the hierarchies for deterministic, nondeterministic and probabilistic ordered read-k-times branching programs. Lobachevskii J. Math. 37(6), 682\u2013703 (2016)","journal-title":"Lobachevskii J. Math."},{"key":"14_CR19","doi-asserted-by":"crossref","unstructured":"Khadiev, K., Ibrahimov, R.: Width hierarchies for quantum and classical ordered binary decision diagrams with repeated test. In: Proceedings of the Fourth Russian Finnish Symposium on Discrete Mathematics. TUCS Lecture Notes, no. 26. Turku Centre for Computer Science (2017)","DOI":"10.1007\/978-3-319-58747-9_16"},{"key":"14_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1007\/978-3-319-58747-9_16","volume-title":"Computer Science \u2013 Theory and Applications","author":"K Khadiev","year":"2017","unstructured":"Khadiev, K., Khadieva, A.: Reordering method and hierarchies for quantum and classical ordered binary decision diagrams. In: Weil, P. (ed.) CSR 2017. LNCS, vol. 10304, pp. 162\u2013175. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-58747-9_16"},{"key":"14_CR21","doi-asserted-by":"crossref","unstructured":"Klauck, H.: On quantum and probabilistic communication: Las Vegas and one-way protocols. In: STOC 2000: Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, pp. 644\u2013651 (2000)","DOI":"10.1145\/335305.335396"},{"key":"14_CR22","unstructured":"Klauck, H.: Quantum communication complexity. arXiv preprint arXiv:quant-ph\/0005032 (2000)"},{"key":"14_CR23","doi-asserted-by":"crossref","unstructured":"Klauck, H.: Lower bounds for quantum communication complexity. In: Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science, pp. 288\u2013297. IEEE (2001)","DOI":"10.1109\/SFCS.2001.959903"},{"issue":"1","key":"14_CR24","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1137\/S0097539702405620","volume":"37","author":"H Klauck","year":"2007","unstructured":"Klauck, H.: Lower bounds for quantum communication complexity. SIAM J. Comput. 37(1), 20\u201346 (2007)","journal-title":"SIAM J. Comput."},{"key":"14_CR25","doi-asserted-by":"crossref","unstructured":"Klauck, H., Nayak, A., Ta-Shma, A., Zuckerman, D.: Interaction in quantum communication and the complexity of set disjointness. In: Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing, pp. 124\u2013133. ACM (2001)","DOI":"10.1145\/380752.380786"},{"issue":"6","key":"14_CR26","doi-asserted-by":"crossref","first-page":"1970","DOI":"10.1109\/TIT.2007.896888","volume":"53","author":"H Klauck","year":"2007","unstructured":"Klauck, H., Nayak, A., Ta-Shma, A., Zuckerman, D.: Interaction in quantum communication. IEEE Trans. Inf. Theory 53(6), 1970\u20131982 (2007)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"3","key":"14_CR27","doi-asserted-by":"crossref","first-page":"368","DOI":"10.1002\/rsa.20232","volume":"34","author":"N Linial","year":"2009","unstructured":"Linial, N., Shraibman, A.: Lower bounds in communication complexity based on factorization norms. Random Struct. Algorithms 34(3), 368\u2013394 (2009)","journal-title":"Random Struct. Algorithms"},{"issue":"1\u20132","key":"14_CR28","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1016\/S0304-3975(98)00191-1","volume":"237","author":"C Moore","year":"2000","unstructured":"Moore, C., Crutchfield, J.P.: Quantum automata and quantum grammars. Theoret. Comput. Sci. 237(1\u20132), 275\u2013306 (2000)","journal-title":"Theoret. Comput. Sci."},{"key":"14_CR29","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.-Z., Eades, P., Estivill-Castro, V., Lin, X., Sharma, A. (eds.) COCOON 2000. LNCS, vol. 1858, pp. 467\u2013476. Springer, Heidelberg (2000). https:\/\/doi.org\/10.1007\/3-540-44968-X_46"},{"key":"14_CR30","doi-asserted-by":"crossref","unstructured":"Nisan, N., Widgerson, A.: Rounds in communication complexity revisited. In: Proceedings of the Twenty-Third Annual ACM Symposium on Theory of Computing, pp. 419\u2013429. ACM (1991)","DOI":"10.1145\/103418.103463"},{"key":"14_CR31","doi-asserted-by":"crossref","unstructured":"Raz, R.: Exponential separation of quantum and classical communication complexity. In: Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, pp. 358\u2013367. ACM (1999)","DOI":"10.1145\/301250.301343"},{"key":"14_CR32","unstructured":"Sauerhoff, M.: Quantum vs. classical read-once branching programs. In: Complexity of Boolean Functions. Dagstuhl Seminar Proceedings, no. 06111. Internationales Begegnungs- und Forschungszentrum f\u00fcr Informatik (2006)"},{"issue":"1\u20133","key":"14_CR33","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/j.tcs.2004.12.031","volume":"334","author":"M Sauerhoff","year":"2005","unstructured":"Sauerhoff, M., Sieling, D.: Quantum branching programs and space-bounded nonuniform quantum complexity. Theoret. Comput. Sci. 334(1\u20133), 177\u2013225 (2005)","journal-title":"Theoret. Comput. Sci."},{"issue":"4","key":"14_CR34","doi-asserted-by":"publisher","first-page":"585","DOI":"10.1134\/S1990478908040145","volume":"2","author":"AV Vasiliev","year":"2008","unstructured":"Vasiliev, A.V.: Functions computable by boolean circuits of logarithmic depth and branching programs of a special type. J. Appl. Ind. Math. 2(4), 585\u2013590 (2008). https:\/\/doi.org\/10.1134\/S1990478908040145","journal-title":"J. Appl. Ind. Math."},{"key":"14_CR35","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898719789","volume-title":"Branching Programs and Binary Decision Diagrams: Theory and Applications","author":"I Wegener","year":"2000","unstructured":"Wegener, I.: Branching Programs and Binary Decision Diagrams: Theory and Applications. SIAM, Philadelphia (2000)"},{"issue":"2","key":"14_CR36","first-page":"19","volume":"12","author":"A Yakary\u0131lmaz","year":"2010","unstructured":"Yakary\u0131lmaz, A., Say, A.C.C.: Succinctness of two-way probabilistic and quantum finite automata. Discret. Math. Theoret. Comput. Sci. 12(2), 19\u201340 (2010)","journal-title":"Discret. Math. Theoret. Comput. Sci."},{"key":"14_CR37","unstructured":"Zheng, S., Gruska, J.: Time-space tradeoffs for two-way finite automata. arXiv preprint arXiv:1507.01346 (2015)"}],"container-title":["Lecture Notes in Computer Science","SOFSEM 2018: Theory and Practice of Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-73117-9_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,8]],"date-time":"2019-10-08T11:45:00Z","timestamp":1570535100000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-73117-9_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,12,22]]},"ISBN":["9783319731162","9783319731179"],"references-count":37,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-73117-9_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,12,22]]}}}