{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:46Z","timestamp":1740109306146,"version":"3.37.3"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2019,9,23]],"date-time":"2019-09-23T00:00:00Z","timestamp":1569196800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,9,23]],"date-time":"2019-09-23T00:00:00Z","timestamp":1569196800000},"content-version":"vor","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":[[2020,4]]},"DOI":"10.1007\/s00453-019-00627-z","type":"journal-article","created":{"date-parts":[[2019,9,23]],"date-time":"2019-09-23T14:02:38Z","timestamp":1569247358000},"page":"980-1005","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Extended Learning Graphs for Triangle Finding"],"prefix":"10.1007","volume":"82","author":[{"given":"Titouan","family":"Carette","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4380-1399","authenticated-orcid":false,"given":"Mathieu","family":"Lauri\u00e8re","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fr\u00e9d\u00e9ric","family":"Magniez","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,9,23]]},"reference":[{"key":"627_CR1","doi-asserted-by":"crossref","unstructured":"Aaronson, S., Ben-David, S., Kothari, R.: Separations in query complexity using cheat sheets. In: Proceedings of 48th ACM Symposium on Theory of Computing, pp. 863\u2013876 (2016)","DOI":"10.1145\/2897518.2897644"},{"issue":"3","key":"627_CR2","doi-asserted-by":"publisher","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":"627_CR3","unstructured":"Ambainis, A.: Understanding quantum algorithms via query complexity (2017). \narXiv:1712.06349"},{"key":"627_CR4","doi-asserted-by":"crossref","unstructured":"Ambainis, A., Balodis, K., Belovs, A., Lee, T., Santha, M., Smotrovs, J.: Separations in query complexity based on pointer functions. In: Proceedings of 48th ACM Symposium on Theory of Computing, pp. 800\u2013813 (2016)","DOI":"10.1145\/2897518.2897524"},{"issue":"4","key":"627_CR5","doi-asserted-by":"publisher","first-page":"778","DOI":"10.1145\/502090.502097","volume":"48","author":"R Beals","year":"2001","unstructured":"Beals, R., Buhrman, H., Cleve, R., Mosca, M., Wolf, R.: Quantum lower bounds by polynomials. J. ACM 48(4), 778\u2013797 (2001)","journal-title":"J. ACM"},{"key":"627_CR6","doi-asserted-by":"crossref","unstructured":"Belovs, A.: Learning-graph-based quantum algorithm for k-distinctness. In: Prooceedings of 53rd IEEE Symposium on Foundations of Computer Science, pp. 207\u2013216 (2012)","DOI":"10.1109\/FOCS.2012.18"},{"key":"627_CR7","doi-asserted-by":"crossref","unstructured":"Belovs, A.: Span programs for functions with constant-sized 1-certificates. In: Proceedings of 44th Symposium on Theory of Computing Conference, pp. 77\u201384 (2012)","DOI":"10.1145\/2213977.2213985"},{"key":"627_CR8","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/978-3-642-39206-1_10","volume-title":"Automata, Languages, and Programming","author":"Aleksandrs Belovs","year":"2013","unstructured":"Belovs, A., Childs, A., Jeffery, S., Kothari, R., Magniez, F.: Time-efficient quantum walks for 3-distinctness. In: Proceedings of 40th International Colloquium on Automata, Languages and Programming, pp. 105\u2013122 (2013)"},{"key":"627_CR9","unstructured":"Belovs, A., Lee, T.: Quantum algorithm for k-distinctness with prior knowledge on the input. Tech. Rep. \narXiv:1108.3022\n\n (2011)"},{"key":"627_CR10","doi-asserted-by":"crossref","unstructured":"Belovs, A., Rosmanis, A.: On the power of non-adaptive learning graphs. In: Proceedings of 28th IEEE Conference on Computational Complexity, pp. 44\u201355 (2013)","DOI":"10.1109\/CCC.2013.14"},{"key":"627_CR11","doi-asserted-by":"publisher","unstructured":"Brassard, G., H\u00f8yer, P., Mosca, M., Tapp, A.: Quantum amplitude amplification and estimation. In: Quantum computation and information (Washington, DC, 2000), Contemp. Math., vol. 305, pp. 53\u201374. Amer. Math. Soc., Providence, RI (2002). \nhttps:\/\/doi.org\/10.1090\/conm\/305\/05215","DOI":"10.1090\/conm\/305\/05215"},{"issue":"6","key":"627_CR12","doi-asserted-by":"publisher","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., Wolf, R.: Quantum algorithms for element distinctness. SIAM J. Comput. 34(6), 1324\u20131330 (2005)","journal-title":"SIAM J. Comput."},{"key":"627_CR13","unstructured":"Childs, A: Lecture notes on quantum algorithms. Technical report, University of Maryland (2017). \nhttps:\/\/cs.umd.edu\/~amchilds\/qa\/"},{"issue":"1969","key":"627_CR14","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1098\/rspa.1998.0164","volume":"454","author":"R. Cleve","year":"1998","unstructured":"Cleve, R., Ekert, A., Macchiavello, C., Mosca, M.: Quantum algorithms revisited. R. Soc. Lond. Proc. Ser. A Math. Phys. Eng. Sci. 454(1969), 339\u2013354 (1998). \nhttps:\/\/doi.org\/10.1098\/rspa.1998.0164\n\n. Quantum coherence and decoherence (Santa Barbara, CA, 1996)","journal-title":"Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences"},{"key":"627_CR15","doi-asserted-by":"crossref","unstructured":"Le Gall, F.: Improved quantum algorithm for triangle finding via combinatorial arguments. In: Proceedings of 55th IEEE Foundations of Computer Science, pp. 216\u2013225 (2014)","DOI":"10.1109\/FOCS.2014.31"},{"key":"627_CR16","doi-asserted-by":"crossref","unstructured":"Le Gall, F.: Nakajima, S.: Quantum algorithm for triangle finding in sparse graphs. In: Proceedings of 26th International Symposium Algorithms and Computation, pp. 590\u2013600 (2015)","DOI":"10.1007\/978-3-662-48971-0_50"},{"key":"627_CR17","doi-asserted-by":"crossref","unstructured":"Grover, L.: A fast quantum mechanical algorithm for database search. In: Proceedings of 28th ACM Symposium on the Theory of Computing, pp. 212\u2013219 (1996)","DOI":"10.1145\/237814.237866"},{"key":"627_CR18","doi-asserted-by":"crossref","unstructured":"H\u00f8yer, P., Lee, T., \u0160palek, R.: Negative weights make adversaries stronger. In: Proceedings of 39th ACM Symposium on Theory of Computing, pp. 526\u2013535 (2007)","DOI":"10.1145\/1250790.1250867"},{"key":"627_CR19","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1007\/3-540-45061-0_25","volume-title":"Automata, Languages and Programming","author":"Peter H\u00f8yer","year":"2003","unstructured":"H\u00f8yer, P., Mosca, M., de\u00a0Wolf, R.: Quantum search on bounded-error imputs. In: Automata, languages and programming, Lecture Notes in Comput. Sci., vol. 2719, pp. 291\u2013299. Springer, Berlin (2003). \nhttps:\/\/doi.org\/10.1007\/3-540-45061-0_25"},{"key":"627_CR20","first-page":"78","volume":"87","author":"P H\u00f8yer","year":"2005","unstructured":"H\u00f8yer, P., \u0160palek, R.: Lower bounds on quantum query complexity. Bull. Eur. Assoc. Theor. Comput. Sci. 87, 78\u2013103 (2005)","journal-title":"Bull. Eur. Assoc. Theor. Comput. Sci."},{"key":"627_CR21","unstructured":"Kitaev, A.: Quantum measurements and the Abelian stabilizer problem. Tech. Rep. \narXiv:quant-ph\/9511026\n\n (1995)"},{"key":"627_CR22","doi-asserted-by":"publisher","unstructured":"Kitaev, A.Y., Shen, A.H., Vyalyi, M.N.: Classical and quantum computation, Graduate Studies in Mathematics, vol.\u00a047. American Mathematical Society, Providence, RI (2002). \nhttps:\/\/doi.org\/10.1090\/gsm\/047\n\n. Translated from the 1999 Russian original by Lester J. Senechal","DOI":"10.1090\/gsm\/047"},{"issue":"2","key":"627_CR23","doi-asserted-by":"publisher","first-page":"459","DOI":"10.1007\/s00453-015-0084-9","volume":"77","author":"Troy Lee","year":"2015","unstructured":"Lee, T., Magniez, F., Santha, M.: Improved quantum query algorithms for triangle detection and associativity testing. Algorithmica 77, 459\u2013486 (2017)","journal-title":"Algorithmica"},{"key":"627_CR24","doi-asserted-by":"crossref","unstructured":"Lee, T., Mittal, R., Reichardt, B., \u0160palek, R., Szegedy, M.: Quantum query complexity of state conversion. In: Proceedings of 52nd IEEE Symposium on Foundations of Computer Science, pp. 344\u2013353 (2011)","DOI":"10.1109\/FOCS.2011.75"},{"issue":"1","key":"627_CR25","doi-asserted-by":"publisher","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."},{"issue":"2","key":"627_CR26","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 J. Comput. 37(2), 413\u2013424 (2007)","journal-title":"SIAM J. Comput."},{"issue":"6","key":"627_CR27","doi-asserted-by":"publisher","first-page":"999","DOI":"10.1137\/0220062","volume":"20","author":"N Nisan","year":"1991","unstructured":"Nisan, N.: Crew prams and decision trees. SIAM J. Comput. 20(6), 999\u20131007 (1991)","journal-title":"SIAM J. Comput."},{"key":"627_CR28","doi-asserted-by":"crossref","unstructured":"Reichardt, B.: Reflections for quantum query algorithms. In: Proceedings of 22nd ACM-SIAM Symposium on Discrete Algorithms, pp. 560\u2013569 (2011)","DOI":"10.1137\/1.9781611973082.44"},{"issue":"5","key":"627_CR29","doi-asserted-by":"publisher","first-page":"1484","DOI":"10.1137\/S0097539795293172","volume":"26","author":"P Shor","year":"1997","unstructured":"Shor, P.: Algorithms for quantum computation: Discrete logarithm and factoring. SIAM J. Comput. 26(5), 1484\u20131509 (1997)","journal-title":"SIAM J. Comput."},{"key":"627_CR30","unstructured":"S\u0306palek, R.: Quantum algorithms, lower bounds, and time-space tradeoffs. PhD thesis (2006)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00627-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-019-00627-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00627-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,9,21]],"date-time":"2020-09-21T23:07:10Z","timestamp":1600729630000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-019-00627-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,9,23]]},"references-count":30,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,4]]}},"alternative-id":["627"],"URL":"https:\/\/doi.org\/10.1007\/s00453-019-00627-z","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2019,9,23]]},"assertion":[{"value":"8 September 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 August 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 September 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}