{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T11:46:19Z","timestamp":1725795979878},"publisher-location":"Cham","reference-count":24,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319084039"},{"type":"electronic","value":"9783319084046"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-08404-6_29","type":"book-chapter","created":{"date-parts":[[2014,6,25]],"date-time":"2014-06-25T03:55:08Z","timestamp":1403668508000},"page":"331-343","source":"Crossref","is-referenced-by-count":5,"title":["Quantum Algorithms for Matrix Products over Semirings"],"prefix":"10.1007","author":[{"given":"Fran\u00e7ois","family":"Le Gall","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Harumichi","family":"Nishimura","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"29_CR1","doi-asserted-by":"crossref","unstructured":"Amossen, R.R., Pagh, R.: Faster join-projects and sparse matrix multiplications. In: Proceedings of ICDT, pp. 121\u2013126 (2009)","DOI":"10.1145\/1514894.1514909"},{"issue":"4-5","key":"29_CR2","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1002\/(SICI)1521-3978(199806)46:4\/5<493::AID-PROP493>3.0.CO;2-P","volume":"46","author":"M. Boyer","year":"1998","unstructured":"Boyer, M., Brassard, G., H\u00f8yer, P., Tapp, A.: Tight bounds on quantum searching. Fortschritte der Physik\u00a046(4-5), 493\u2013505 (1998)","journal-title":"Fortschritte der Physik"},{"key":"29_CR3","doi-asserted-by":"crossref","unstructured":"Buhrman, H., \u0160palek, R.: Quantum verification of matrix products. In: Proceedings of SODA, pp. 880\u2013889 (2006)","DOI":"10.1145\/1109557.1109654"},{"key":"29_CR4","doi-asserted-by":"crossref","unstructured":"B\u00fcrgisser, P., Clausen, M., Shokrollahi, M.A.: Algebraic complexity theory. Springer (1997)","DOI":"10.1007\/978-3-662-03338-8"},{"key":"29_CR5","doi-asserted-by":"crossref","unstructured":"Duan, R., Pettie, S.: Fast algorithms for (max, min)-matrix multiplication and bottleneck shortest paths. In: Proceedings of SODA, pp. 384\u2013391 (2009)","DOI":"10.1137\/1.9781611973068.43"},{"key":"29_CR6","unstructured":"Dubois, D., Prade, H.: Fuzzy sets and systems: Theory and applications. Academic Press (1980)"},{"key":"29_CR7","unstructured":"D\u00fcrr, C., H\u00f8yer, P.: A quantum algorithm for finding the minimum. arXiv:quant-ph\/9607014 (1996)"},{"key":"29_CR8","doi-asserted-by":"crossref","unstructured":"Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Proceedings of STOC, pp. 212\u2013219 (1996)","DOI":"10.1145\/237814.237866"},{"issue":"2","key":"29_CR9","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1006\/jcom.1998.0476","volume":"14","author":"X. Huang","year":"1998","unstructured":"Huang, X., Pan, V.Y.: Fast rectangular matrix multiplication and applications. Journal of Complexity\u00a014(2), 257\u2013299 (1998)","journal-title":"Journal of Complexity"},{"key":"29_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"522","DOI":"10.1007\/978-3-642-31594-7_44","volume-title":"Automata, Languages, and Programming","author":"S. Jeffery","year":"2012","unstructured":"Jeffery, S., Kothari, R., Magniez, F.: Improving quantum query complexity of Boolean matrix multiplication using graph collision. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012, Part I. LNCS, vol.\u00a07391, pp. 522\u2013532. Springer, Heidelberg (2012)"},{"key":"29_CR11","doi-asserted-by":"crossref","unstructured":"Le Gall, F.: Faster algorithms for rectangular matrix multiplication. In: Proceedings of FOCS, pp. 514\u2013523 (2012)","DOI":"10.1109\/FOCS.2012.80"},{"key":"29_CR12","doi-asserted-by":"crossref","unstructured":"Le Gall, F.: Improved output-sensitive quantum algorithms for Boolean matrix multiplication. In: Proceedings of SODA, pp. 1464\u20131476 (2012)","DOI":"10.1137\/1.9781611973099.116"},{"key":"29_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"639","DOI":"10.1007\/978-3-642-35261-4_66","volume-title":"Algorithms and Computation","author":"F. Gall Le","year":"2012","unstructured":"Le Gall, F.: A time-efficient output-sensitive quantum algorithm for Boolean matrix multiplication. In: Chao, K.-M., Hsu, T.-S., Lee, D.-T. (eds.) ISAAC 2012. LNCS, vol.\u00a07676, pp. 639\u2013648. Springer, Heidelberg (2012)"},{"key":"29_CR14","doi-asserted-by":"crossref","unstructured":"Le Gall, F.: Powers of tensors and fast matrix multiplication. In: Proceedings of ISSAC (to appear, 2014)","DOI":"10.1145\/2608628.2608664"},{"key":"29_CR15","unstructured":"Le Gall, F., Nishimura, H.: Quantum algorithms for matrix products over semirings. Full version of the present paper, available as arXiv:1310.3898"},{"issue":"2","key":"29_CR16","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1137\/050643684","volume":"37","author":"F. Magniez","year":"2007","unstructured":"Magniez, F., Santha, M., Szegedy, M.: Quantum algorithms for the triangle problem. SIAM Journal on Computing\u00a037(2), 413\u2013424 (2007)","journal-title":"SIAM Journal on Computing"},{"issue":"5","key":"29_CR17","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1016\/0020-0190(91)90071-O","volume":"38","author":"J. Matou\u0161ek","year":"1991","unstructured":"Matou\u0161ek, J.: Computing dominances in E\n                \n                  n\n                . Information Processing Letters\u00a038(5), 277\u2013278 (1991)","journal-title":"Information Processing Letters"},{"key":"29_CR18","unstructured":"Shapira, A., Yuster, R., Zwick, U.: All-pairs bottleneck paths in vertex weighted graphs. In: Proceedings of SODA, pp. 978\u2013985 (2007)"},{"key":"29_CR19","unstructured":"Vassilevska, V.: Efficient Algorithms for Path Problems in Weighted Graphs. PhD thesis, Carnegie Mellon University (2008)"},{"key":"29_CR20","doi-asserted-by":"crossref","unstructured":"Vassilevska, V., Williams, R.: Finding a maximum weight triangle in n\n                3\u2009\u2212\u2009\u03b4\n                 time, with applications. In: Proceedings of STOC, pp. 225\u2013231 (2006)","DOI":"10.1145\/1132516.1132550"},{"issue":"1","key":"29_CR21","doi-asserted-by":"publisher","first-page":"173","DOI":"10.4086\/toc.2009.v005a009","volume":"5","author":"V. Vassilevska","year":"2009","unstructured":"Vassilevska, V., Williams, R., Yuster, R.: All pairs bottleneck paths and max-min matrix products in truly subcubic time. Theory of Computing\u00a05(1), 173\u2013189 (2009)","journal-title":"Theory of Computing"},{"key":"29_CR22","doi-asserted-by":"crossref","unstructured":"Vassilevska Williams, V.: Multiplying matrices faster than Coppersmith-Winograd. In: Proceedings of STOC, pp. 887\u2013898 (2012)","DOI":"10.1145\/2213977.2214056"},{"key":"29_CR23","doi-asserted-by":"crossref","unstructured":"Yuster, R.: Efficient algorithms on sets of permutations, dominance, and real-weighted APSP. In: Proceedings of SODA, pp. 950\u2013957 (2009)","DOI":"10.1137\/1.9781611973068.103"},{"issue":"1","key":"29_CR24","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1145\/1077464.1077466","volume":"1","author":"R. Yuster","year":"2005","unstructured":"Yuster, R., Zwick, U.: Fast sparse matrix multiplication. ACM Transactions on Algorithms\u00a01(1), 2\u201313 (2005)","journal-title":"ACM Transactions on Algorithms"}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory \u2013 SWAT 2014"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-08404-6_29","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,27]],"date-time":"2019-05-27T04:14:32Z","timestamp":1558930472000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-08404-6_29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319084039","9783319084046"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-08404-6_29","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}