{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,24]],"date-time":"2026-03-24T08:08:55Z","timestamp":1774339735092,"version":"3.50.1"},"publisher-location":"Cham","reference-count":67,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319983547","type":"print"},{"value":"9783319983554","type":"electronic"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-98355-4_9","type":"book-chapter","created":{"date-parts":[[2018,8,8]],"date-time":"2018-08-08T10:34:57Z","timestamp":1533724497000},"page":"129-155","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":15,"title":["Classical and Quantum Computations with Restricted Memory"],"prefix":"10.1007","author":[{"given":"Farid","family":"Ablayev","sequence":"first","affiliation":[]},{"given":"Marat","family":"Ablayev","sequence":"additional","affiliation":[]},{"given":"Kamil","family":"Khadiev","sequence":"additional","affiliation":[]},{"given":"Alexander","family":"Vasiliev","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,8,9]]},"reference":[{"key":"9_CR1","doi-asserted-by":"crossref","unstructured":"Ablayev, F.: Randomization and nondeterminism are incomparable for ordered read-once branching programs. In: Electronic Colloquium on Computational Complexity (ECCC) (021) (1997)","DOI":"10.1007\/3-540-63165-8_177"},{"issue":"2","key":"9_CR2","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1134\/S199508021502002X","volume":"36","author":"F Ablayev","year":"2015","unstructured":"Ablayev, F., Ablayev, M.: Quantum hashing via $$\\varepsilon $$-universal hashing constructions and classical fingerprinting. Lobachevskii J. Math. 36(2), 89\u201396 (2015). https:\/\/doi.org\/10.1134\/S199508021502002X","journal-title":"Lobachevskii J. Math."},{"key":"9_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1007\/978-3-319-73117-9_14","volume-title":"SOFSEM 2018: Theory and Practice of Computer Science","author":"F Ablayev","year":"2018","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. In: Tjoa, A.M., Bellatreche, L., Biffl, S., van Leeuwen, J., Wiedermann, J. (eds.) SOFSEM 2018. LNCS, vol. 10706, pp. 197\u2013211. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-73117-9_14"},{"key":"9_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":"9_CR5","doi-asserted-by":"publisher","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."},{"issue":"6","key":"9_CR6","doi-asserted-by":"publisher","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). https:\/\/doi.org\/10.1134\/S199508021606007X","journal-title":"Lobachevskii J. Math."},{"key":"9_CR7","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"},{"key":"9_CR8","unstructured":"Ablayev, F., Karpinski, M.: On the power of randomized ordered branching programs. In: Electronic Colloquium on Computational Complexity (ECCC) (004) (1998)"},{"issue":"12","key":"9_CR9","doi-asserted-by":"publisher","first-page":"125204","DOI":"10.1088\/1612-2011\/12\/12\/125204","volume":"12","author":"F Ablayev","year":"2015","unstructured":"Ablayev, F., Ablayev, M.: On the concept of cryptographic quantum hashing. Laser Phys. Lett. 12(12), 125204 (2015). http:\/\/stacks.iop.org\/1612-202X\/12\/i=12\/a=125204","journal-title":"Laser Phys. Lett."},{"key":"9_CR10","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"},{"issue":"3","key":"9_CR11","doi-asserted-by":"publisher","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":"9_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","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, F., Monien, B. (eds.) ICALP 1996. LNCS, vol. 1099, pp. 348\u2013356. Springer, Heidelberg (1996). https:\/\/doi.org\/10.1007\/3-540-61440-0_141"},{"key":"9_CR13","unstructured":"Albers, S.: BRICS, Mini-Course on Competitive Online Algorithms. Aarhus University (1996)"},{"issue":"2","key":"9_CR14","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1002\/rsa.3240050203","volume":"5","author":"N Alon","year":"1994","unstructured":"Alon, N., Roichman, Y.: Random Cayley graphs and expanders. Random Struct. Algorithms 5(2), 271\u2013284 (1994). https:\/\/doi.org\/10.1002\/rsa.3240050203","journal-title":"Random Struct. Algorithms"},{"issue":"1","key":"9_CR15","doi-asserted-by":"publisher","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. Theor. Comput. Sci. 287(1), 299\u2013311 (2002)","journal-title":"Theor. Comput. Sci."},{"issue":"7","key":"9_CR16","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1016\/j.ipl.2012.01.001","volume":"112","author":"A Ambainis","year":"2012","unstructured":"Ambainis, A., Yakary\u0131lmaz, A.: Superiority of exact quantum automata for promise problems. Inf. Process. Lett. 112(7), 289\u2013291 (2012)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"9_CR17","doi-asserted-by":"publisher","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}$$. J. Comput. Syst. Sci. 38(1), 150\u2013164 (1989)","journal-title":"J. Comput. Syst. Sci."},{"key":"9_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"156","DOI":"10.1007\/978-3-642-02927-1_15","volume-title":"Automata, Languages and Programming","author":"L Becchetti","year":"2009","unstructured":"Becchetti, L., Koutsoupias, E.: Competitive analysis of aggregate max in windowed streaming. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009. LNCS, vol. 5555, pp. 156\u2013170. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-02927-1_15"},{"issue":"1","key":"9_CR19","doi-asserted-by":"publisher","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. Theor. Comput. Sci. 205(1), 45\u201360 (1998)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"9_CR20","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. Comput. Complex. 3(1), 1\u201318 (1993)","journal-title":"Comput. Complex."},{"issue":"2","key":"9_CR21","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1145\/3056461","volume":"50","author":"J Boyar","year":"2017","unstructured":"Boyar, J., Favrholdt, L., Kudahl, C., Larsen, K., Mikkelsen, J.: Online algorithms with advice: a survey. ACM Comput. Surv. (CSUR) 50(2), 19 (2017)","journal-title":"ACM Comput. Surv. (CSUR)"},{"key":"9_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1007\/978-3-642-03367-4_11","volume-title":"Algorithms and Data Structures","author":"J Boyar","year":"2009","unstructured":"Boyar, J., Irani, S., Larsen, K.S.: A comparison of performance measures for online algorithms. In: Dehne, F., Gavrilova, M., Sack, J.-R., T\u00f3th, C.D. (eds.) WADS 2009. LNCS, vol. 5664, pp. 119\u2013130. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-03367-4_11"},{"issue":"4","key":"9_CR23","doi-asserted-by":"publisher","first-page":"969","DOI":"10.1007\/s00453-014-9884-6","volume":"72","author":"J Boyar","year":"2015","unstructured":"Boyar, J., Irani, S., Larsen, K.S.: A comparison of performance measures for online algorithms. Algorithmica 72(4), 969\u2013994 (2015)","journal-title":"Algorithmica"},{"issue":"4","key":"9_CR24","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1142\/S0129054115500239","volume":"26","author":"J Boyar","year":"2015","unstructured":"Boyar, J., Larsen, K.S., Maiti, A.: The frequent items problem in online streaming under various performance measures. Int. J. Found. Comput. Sci. 26(4), 413\u2013439 (2015)","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"1","key":"9_CR25","doi-asserted-by":"publisher","first-page":"6","DOI":"10.1016\/j.ipl.2005.11.011","volume":"98","author":"H Brosenne","year":"2006","unstructured":"Brosenne, H., Homeister, M., Waack, S.: Nondeterministic ordered binary decision diagrams with repeated tests and various modes of acceptance. Inf. Process. Lett. 98(1), 6\u201310 (2006)","journal-title":"Inf. Process. Lett."},{"issue":"16","key":"9_CR26","doi-asserted-by":"publisher","first-page":"167902","DOI":"10.1103\/PhysRevLett.87.167902","volume":"87","author":"H Buhrman","year":"2001","unstructured":"Buhrman, H., Cleve, R., Watrous, J., de Wolf, R.: Quantum fingerprinting. Phys. Rev. Lett. 87(16), 167902 (2001). https:\/\/doi.org\/10.1103\/PhysRevLett.87.167902. http:\/\/www.arXiv.org\/quant-ph\/0102001v1","journal-title":"Phys. Rev. Lett."},{"key":"9_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"436","DOI":"10.1007\/978-3-642-40328-6_31","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"S Chen","year":"2013","unstructured":"Chen, S., Moore, C., Russell, A.: Small-bias sets for nonabelian groups. In: Raghavendra, P., Raskhodnikova, S., Jansen, K., Rolim, J.D.P. (eds.) APPROX\/RANDOM -2013. LNCS, vol. 8096, pp. 436\u2013451. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-40328-6_31"},{"issue":"3","key":"9_CR28","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1145\/1086649.1086670","volume":"36","author":"R Dorrigiv","year":"2005","unstructured":"Dorrigiv, R., L\u00f3pez-Ortiz, A.: A survey of performance measures for on-line algorithms. SIGACT News 36(3), 67\u201381 (2005)","journal-title":"SIGACT News"},{"key":"9_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1007\/BFb0023453","volume-title":"STACS 97","author":"P Duri\u0161","year":"1997","unstructured":"Duri\u0161, P., Hromkovi\u010d, J., Rolim, J.D.P., Schnitger, G.: Las Vegas versus determinism for one-way communication complexity, finite automata, and polynomial-time computations. In: Reischuk, R., Morvan, M. (eds.) STACS 1997. LNCS, vol. 1200, pp. 117\u2013128. Springer, Heidelberg (1997). https:\/\/doi.org\/10.1007\/BFb0023453"},{"key":"9_CR30","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/j.tcs.2014.09.011","volume":"562","author":"Y Giannakopoulos","year":"2015","unstructured":"Giannakopoulos, Y., Koutsoupias, E.: Competitive analysis of maintaining frequent items of a stream. Theor. Comput. Sci. 562, 23\u201332 (2015)","journal-title":"Theor. Comput. Sci."},{"key":"9_CR31","unstructured":"Gottesman, D., Chuang, I.: Quantum digital signatures. Technical report, Cornell University Library, November 2001. http:\/\/arxiv.org\/abs\/quant-ph\/0105032"},{"issue":"1","key":"9_CR32","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1051\/ita:2003007","volume":"37","author":"M Hirvensalo","year":"2003","unstructured":"Hirvensalo, M., Seibert, S.: Lower bounds for Las Vegas automata by information theory. RAIRO-Theor. Inform. Appl. 37(1), 39\u201349 (2003)","journal-title":"RAIRO-Theor. Inform. Appl."},{"key":"9_CR33","unstructured":"Holevo, A.S.: Some estimates of the information transmitted by quantum communication channel (russian). Probl. Pered. Inform. [Probl. Inf. Transm.] 9(3), 3\u201311 (1973)"},{"key":"9_CR34","unstructured":"Homeister, M., Waack, S.: Quantum ordered binary decision diagrams with repeated tests. arXiv preprint quant-ph\/0507258 (2005)"},{"issue":"2","key":"9_CR35","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1007\/s00224-002-1050-x","volume":"36","author":"J Hromkovi\u010d","year":"2003","unstructured":"Hromkovi\u010d, J., Sauerhoff, M.: The power of nondeterminism and randomness for oblivious branching programs. Theory Comput. Syst. 36(2), 159\u2013182 (2003)","journal-title":"Theory Comput. Syst."},{"key":"9_CR36","unstructured":"Hromkovic, J.: Z\u00e1mecnikov\u00e1. design and analysis of randomized algorithms: introduction to design paradigms (2005)"},{"issue":"2","key":"9_CR37","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1006\/inco.2001.3040","volume":"169","author":"J Hromkovi\u010d","year":"2001","unstructured":"Hromkovi\u010d, J., Schnitger, G.: On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata. Inf. Comput. 169(2), 284\u2013296 (2001)","journal-title":"Inf. Comput."},{"key":"9_CR38","unstructured":"Ibrahimov, R., Khadiev, K., Prusis, K., Yakary\u0131lmaz, A.: Zero-error affine, unitary, and probabilistic obdds. Technical report. arXiv 1703.07184 (2017)"},{"key":"9_CR39","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"},{"key":"9_CR40","doi-asserted-by":"crossref","unstructured":"Karlin, A.R., Manasse, M.S., Rudolph, L., Sleator, D.D.: Competitive snoopy caching. In: 1986 27th Annual Symposium on Foundations of Computer Science, pp. 244\u2013254. IEEE (1986)","DOI":"10.1109\/SFCS.1986.14"},{"issue":"2","key":"9_CR41","doi-asserted-by":"publisher","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":"9_CR42","doi-asserted-by":"publisher","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":"9_CR43","unstructured":"Khadiev, K., Khadieva, A.: Quantum automata for online minimization problems. In: Ninth Workshop on NCMA 2017 Short Papers, pp. 25\u201333. Institute fur Computersprachen TU Wien (2017)"},{"key":"9_CR44","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":"9_CR45","unstructured":"Khadiev, K., Khadieva, A., Kravchenko, D., Rivosh, A., Yamilov, R., Mannapov, I.: Quantum versus classical online algorithms with advice and logarithmic space. arXiv:1710.09595 (2017)"},{"key":"9_CR46","unstructured":"Khadiev, K., Ziatdinov, M., Mannapov, I., Khadieva, A., Yamilov, R.: Quantum online streaming algorithms with constant number of advice bits. arXiv:1802.05134 (2018)"},{"key":"9_CR47","doi-asserted-by":"crossref","unstructured":"Khadiev, K., Khadieva, A., Mannapov, I.: Quantum online algorithms with respect to space complexity. arXiv:1709.08409 (2017)","DOI":"10.1134\/S1995080218090421"},{"issue":"6","key":"9_CR48","doi-asserted-by":"publisher","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"},{"key":"9_CR49","doi-asserted-by":"crossref","unstructured":"Klauck, H.: On quantum and probabilistic communication: Las vegas and one-way protocols. In: Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, STOC 2000, pp. 644\u2013651 (2000)","DOI":"10.1145\/335305.335396"},{"key":"9_CR50","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-42749-2","volume-title":"An Introduction to Online Computation: Determinism, Randomization, Advice","author":"D Komm","year":"2016","unstructured":"Komm, D.: An Introduction to Online Computation: Determinism, Randomization, Advice. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-319-42749-2"},{"issue":"3","key":"9_CR51","doi-asserted-by":"publisher","first-page":"1501","DOI":"10.1007\/s11128-012-0421-8","volume":"12","author":"D Li","year":"2013","unstructured":"Li, D., Zhang, J., Guo, F.Z., Huang, W., Wen, Q.Y., Chen, H.: Discrete-time interacting quantum walks and quantum hash schemes. Quantum Inf. Process. 12(3), 1501\u20131513 (2013). https:\/\/doi.org\/10.1007\/s11128-012-0421-8","journal-title":"Quantum Inf. Process."},{"issue":"6","key":"9_CR52","doi-asserted-by":"publisher","first-page":"2167","DOI":"10.1007\/s11128-012-0516-2","volume":"12","author":"D Li","year":"2013","unstructured":"Li, D., Zhang, J., Ma, X.W., Zhang, W.W., Wen, Q.Y.: Analysis of the two-particle controlled interacting quantum walks. Quantum Inf. Process. 12(6), 2167\u20132176 (2013). https:\/\/doi.org\/10.1007\/s11128-012-0516-2","journal-title":"Quantum Inf. Process."},{"key":"9_CR53","doi-asserted-by":"crossref","unstructured":"Muthukrishnan, S., et al.: Data streams: algorithms and applications. Found. Trends$${\\textregistered }$$ Theor. Comput. Sci. 1(2), 117\u2013236 (2005)","DOI":"10.1561\/0400000002"},{"key":"9_CR54","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":"9_CR55","doi-asserted-by":"publisher","unstructured":"Naor, J., Naor, M.: Small-bias probability spaces: efficient constructions and applications. In: Proceedings of the Twenty-second Annual ACM Symposium on Theory of Computing, STOC 1990, pp. 213\u2013223. ACM, New York (1990). https:\/\/doi.org\/10.1145\/100216.100244","DOI":"10.1145\/100216.100244"},{"key":"9_CR56","doi-asserted-by":"publisher","unstructured":"Nayak, A.: Optimal lower bounds for quantum automata and random access codes. In: 1999 40th Annual Symposium on Foundations of Computer Science, pp. 369\u2013376 (1999). https:\/\/doi.org\/10.1109\/SFFCS.1999.814608","DOI":"10.1109\/SFFCS.1999.814608"},{"key":"9_CR57","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":"9_CR58","unstructured":"Sauerhoff, M.: Quantum vs. classical read-once branching programs. In: Krause, M., Pudl\u00e1k, P., Reischuk, R., van Melkebeek, D. (eds.) Complexity of Boolean Functions. No. 06111 in Dagstuhl Seminar Proceedings, Internationales Begegnungs- und Forschungszentrum f\u00fcr Informatik (IBFI), Schloss Dagstuhl, Germany (2006). http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2006\/616"},{"issue":"1\u20133","key":"9_CR59","doi-asserted-by":"publisher","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. Theor. Comput. Sci. 334(1\u20133), 177\u2013225 (2005)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"9_CR60","doi-asserted-by":"publisher","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. Theor. Comput. Sci. 334(1), 177\u2013225 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"9_CR61","doi-asserted-by":"crossref","unstructured":"Thathachar, J.S.: On separating the read-k-times branching program hierarchy. In: Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, pp. 653\u2013662. ACM (1998)","DOI":"10.1145\/276698.276881"},{"issue":"4","key":"9_CR62","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":"9_CR63","doi-asserted-by":"crossref","unstructured":"Vasiliev, A.: Quantum hashing for finite abelian groups. Lobachevskii J. Math. 37(6), 751\u2013754 (2016). http:\/\/arxiv.org\/abs\/1603.02209","DOI":"10.1134\/S1995080216060184"},{"key":"9_CR64","doi-asserted-by":"publisher","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":"9_CR65","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. Discrete Math. Theor. Comput. Sci. 12(2), 19\u201340 (2010)","journal-title":"Discrete Math. Theor. Comput. Sci."},{"key":"9_CR66","doi-asserted-by":"publisher","first-page":"19788","DOI":"10.1038\/srep19788","volume":"6","author":"YG Yang","year":"2016","unstructured":"Yang, Y.G., Xu, P., Yang, R., Zhou, Y.H., Shi, W.M.: Quantum hash function and its application to privacy amplification in quantum key distribution, pseudorandom number generation and image encryption. Sci. Rep. 6, 19788 (2016). https:\/\/doi.org\/10.1038\/srep19788","journal-title":"Sci. Rep."},{"key":"9_CR67","volume-title":"Quantum Online Algorithms","author":"Q Yuan","year":"2009","unstructured":"Yuan, Q.: Quantum Online Algorithms. University of California, Santa Barbara (2009)"}],"container-title":["Lecture Notes in Computer Science","Adventures Between Lower Bounds and Higher Altitudes"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-98355-4_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,13]],"date-time":"2024-03-13T16:55:51Z","timestamp":1710348951000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-98355-4_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319983547","9783319983554"],"references-count":67,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-98355-4_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"9 August 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}