{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,29]],"date-time":"2025-10-29T03:41:43Z","timestamp":1761709303287,"version":"3.37.3"},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2017,1,5]],"date-time":"2017-01-05T00:00:00Z","timestamp":1483574400000},"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":["Algorithmica"],"published-print":{"date-parts":[[2017,11]]},"DOI":"10.1007\/s00453-016-0267-z","type":"journal-article","created":{"date-parts":[[2017,1,5]],"date-time":"2017-01-05T14:07:44Z","timestamp":1483625264000},"page":"941-959","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Quantum Algorithm for Triangle Finding in Sparse Graphs"],"prefix":"10.1007","volume":"79","author":[{"given":"Fran\u00e7ois","family":"Le Gall","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9348-278X","authenticated-orcid":false,"given":"Shogo","family":"Nakajima","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,1,5]]},"reference":[{"key":"267_CR1","first-page":"354","volume":"17","author":"N Alon","year":"1997","unstructured":"Alon, N., Yuster, R., Zwick, U.: Finding and counting given length cycles. Algorithmica 17, 354\u2013364 (1997)","journal-title":"Algorithmica"},{"issue":"1","key":"267_CR2","doi-asserted-by":"crossref","first-page":"210","DOI":"10.1137\/S0097539705447311","volume":"37","author":"A Ambainis","year":"2007","unstructured":"Ambainis, A.: Quantum walk algorithm for element distinctness. SIAM J. Comput. 37(1), 210\u2013239 (2007)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"267_CR3","doi-asserted-by":"crossref","first-page":"786","DOI":"10.1007\/s00224-009-9219-1","volume":"47","author":"A Ambainis","year":"2010","unstructured":"Ambainis, A.: Quantum search with variable times. Theory Comput. Syst. 47(3), 786\u2013807 (2010)","journal-title":"Theory Comput. Syst."},{"key":"267_CR4","doi-asserted-by":"crossref","unstructured":"Belovs, A.: Span programs for functions with constant-sized 1-certificates: extended abstract. In: Proceedings of the 44th Symposium on Theory of Computing, pp. 77\u201384 (2012)","DOI":"10.1145\/2213977.2213985"},{"key":"267_CR5","doi-asserted-by":"crossref","unstructured":"Brassard, G., H\u00f8yer, P., Tapp, A.: Quantum counting. In: Proceedings of the 25th International Colloquium on Automata, Languages and Programming, pp. 820\u2013831 (1998)","DOI":"10.1007\/BFb0055105"},{"issue":"6","key":"267_CR6","doi-asserted-by":"crossref","first-page":"1324","DOI":"10.1137\/S0097539702402780","volume":"34","author":"H Buhrman","year":"2005","unstructured":"Buhrman, H., D\u00fcrr, C., Heiligman, M., H\u00f8yer, P., Magniez, F., Santha, M., de Wolf, R.: Quantum algorithms for element distinctness. SIAM J. Comput. 34(6), 1324\u20131330 (2005)","journal-title":"SIAM J. Comput."},{"issue":"6","key":"267_CR7","doi-asserted-by":"crossref","first-page":"1426","DOI":"10.1137\/110833026","volume":"41","author":"AM Childs","year":"2012","unstructured":"Childs, A.M., Kothari, R.: Quantum query complexity of minor-closed graph properties. SIAM J. Comput. 41(6), 1426\u20131450 (2012)","journal-title":"SIAM J. Comput."},{"key":"267_CR8","doi-asserted-by":"crossref","unstructured":"Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Proceedings of the 28th Symposium on the Theory of Computing, pp. 212\u2013219 (1996)","DOI":"10.1145\/237814.237866"},{"issue":"4","key":"267_CR9","doi-asserted-by":"crossref","first-page":"413","DOI":"10.1137\/0207033","volume":"7","author":"A Itai","year":"1978","unstructured":"Itai, A., Rodeh, M.: Finding a minimum circuit in a graph. SIAM J. Comput. 7(4), 413\u2013423 (1978)","journal-title":"SIAM J. Comput."},{"key":"267_CR10","volume-title":"Random Graphs","author":"S Janson","year":"2011","unstructured":"Janson, S., Luczak, T.: Random Graphs. Wiley, New York (2011)"},{"key":"267_CR11","doi-asserted-by":"crossref","unstructured":"Jeffery, S., Kothari, R., Magniez, F.: Nested quantum walks with quantum data structures. In: Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1474\u20131485 (2013)","DOI":"10.1137\/1.9781611973105.106"},{"key":"267_CR12","doi-asserted-by":"crossref","unstructured":"Le Gall, F.: Improved quantum algorithm for triangle finding via combinatorial arguments. In: Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, pp. 216\u2013225 (2014)","DOI":"10.1109\/FOCS.2014.31"},{"key":"267_CR13","doi-asserted-by":"crossref","unstructured":"Lee, T., Magniez, F., Santha, M.: Improved quantum query algorithms for triangle finding and associativity testing. In: Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1486\u20131502 (2013)","DOI":"10.1137\/1.9781611973105.107"},{"issue":"2","key":"267_CR14","doi-asserted-by":"crossref","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 J. Comput. 37(2), 413\u2013424 (2007)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"267_CR15","doi-asserted-by":"crossref","first-page":"142","DOI":"10.1137\/090745854","volume":"40","author":"F Magniez","year":"2011","unstructured":"Magniez, F., Nayak, A., Roland, J., Santha, M.: Search via quantum walk. SIAM J. Comput. 40(1), 142\u2013164 (2011)","journal-title":"SIAM J. Comput."},{"key":"267_CR16","doi-asserted-by":"crossref","unstructured":"Patrascu, M.: Towards polynomial lower bounds for dynamic problems. In: Proceedings of the 42nd Symposium on Theory of Computing, pp. 603\u2013610 (2010)","DOI":"10.1145\/1806689.1806772"},{"key":"267_CR17","doi-asserted-by":"crossref","unstructured":"Vassilevska Williams, V., Williams, R.: Subcubic equivalences between path, matrix and triangle problems. In: Proceedings of the 51th Symposium on Foundations of Computer Science, pp. 645\u2013654 (2010)","DOI":"10.1109\/FOCS.2010.67"},{"key":"267_CR18","doi-asserted-by":"crossref","unstructured":"Vassilevska Williams, V., Williams, R.: Finding, minimizing, and counting weighted subgraphs. SIAM J. Comput. 42(3), 831\u2013854 (2013)","DOI":"10.1137\/09076619X"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-016-0267-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0267-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0267-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,17]],"date-time":"2019-09-17T01:48:31Z","timestamp":1568684911000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-016-0267-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,1,5]]},"references-count":18,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,11]]}},"alternative-id":["267"],"URL":"https:\/\/doi.org\/10.1007\/s00453-016-0267-z","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2017,1,5]]}}}