{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,7]],"date-time":"2025-08-07T20:50:37Z","timestamp":1754599837298,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642330896"},{"type":"electronic","value":"9783642330902"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-33090-2_18","type":"book-chapter","created":{"date-parts":[[2012,8,28]],"date-time":"2012-08-28T15:29:11Z","timestamp":1346167751000},"page":"193-204","source":"Crossref","is-referenced-by-count":21,"title":["Span Programs and Quantum Algorithms for st-Connectivity and Claw Detection"],"prefix":"10.1007","author":[{"given":"Aleksandrs","family":"Belovs","sequence":"first","affiliation":[]},{"given":"Ben W.","family":"Reichardt","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"6","key":"18_CR1","doi-asserted-by":"crossref","first-page":"2513","DOI":"10.1137\/080712167","volume":"39","author":"A. Ambainis","year":"2010","unstructured":"Ambainis, A., Childs, A.M., Reichardt, B.W., \u0160palek, R., Zhang, S.: Any AND-OR formula of size N can be evaluated in time N 1\/2\u2009+\u2009o(1) on a quantum computer. SIAM J. Comput.\u00a039(6), 2513\u20132530 (2010); Earlier version in FOCS 2007","journal-title":"SIAM J. Comput."},{"doi-asserted-by":"crossref","unstructured":"Aleliunas, R., Karp, R.M., Lipton, R.J., Lovasz, L., Rackoff, C.: Random walks, universal traversal sequences, and the complexity of maze problems. In: Proc. 20th IEEE FOCS, pp. 218\u2013223 (1979)","key":"18_CR2","DOI":"10.1109\/SFCS.1979.34"},{"issue":"1","key":"18_CR3","doi-asserted-by":"publisher","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. Computing\u00a037(1), 210\u2013239 (2007), arXiv:quant-ph\/0311001","journal-title":"SIAM J. Computing"},{"key":"18_CR4","doi-asserted-by":"publisher","first-page":"844","DOI":"10.1145\/210332.210337","volume":"42","author":"N. Alon","year":"1995","unstructured":"Alon, N., Yuster, R., Zwick, U.: Color-coding. J. ACM\u00a042, 844\u2013856 (1995); Earlier version in STOC 1994","journal-title":"J. ACM"},{"unstructured":"Belovs, A.: Span-program-based quantum algorithm for the rank problem (2011), arXiv:1103.0842","key":"18_CR5"},{"unstructured":"Belovs, A.: Learning-graph-based quantum algorithm for k-distinctness. To Appear in FOCS 2012 (2012), arXiv:1205.1534","key":"18_CR6"},{"unstructured":"Belovs, A.: Span programs for functions with constant-sized 1-certificates. In: Proc. 44th ACM STOC, pp. 77\u201384 (2012), arXiv:1105.4024","key":"18_CR7"},{"unstructured":"Belovs, A., Lee, T.: Quantum algorithm for k-distinctness with prior knowledge on the input (2011), arXiv:1108.3022","key":"18_CR8"},{"unstructured":"Belovs, A., Reichardt, B.W.: Span programs and quantum algorithms for st-connectivity and claw detection (2012), arXiv:1203.2603","key":"18_CR9"},{"unstructured":"Childs, A.M., Kothari, R.: Quantum query complexity of minor-closed graph properties. In: Proc. 28th STACS, pp. 661\u2013672 (2011), arXiv:1011.1443","key":"18_CR10"},{"key":"18_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"481","DOI":"10.1007\/978-3-540-27836-8_42","volume-title":"Automata, Languages and Programming","author":"C. D\u00fcrr","year":"2004","unstructured":"D\u00fcrr, C., Heiligman, M., H\u00f8yer, P., Mhalla, M.: Quantum Query Complexity of Some Graph Problems. In: D\u00edaz, J., Karhum\u00e4ki, J., Lepist\u00f6, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol.\u00a03142, pp. 481\u2013493. Springer, Heidelberg (2004), arXiv:quant-ph\/0401091"},{"doi-asserted-by":"crossref","unstructured":"Doyle, P.G., Laurie Snell, J.: Random Walks and Electric Networks. Carus Mathematical Monographs, vol. 22. Mathematical Association of America (1984), arXiv:math\/0001057 [math.PR]","key":"18_CR12","DOI":"10.5948\/UPO9781614440222"},{"unstructured":"Gavinsky, D., Ito, T.: A quantum query algorithm for the graph collision problem (2012), arXiv:1204.1527","key":"18_CR13"},{"unstructured":"Kimmel, S.: Quantum adversary (upper) bound (2011), arXiv:1101.0797","key":"18_CR14"},{"doi-asserted-by":"crossref","unstructured":"Karchmer, M., Wigderson, A.: On span programs. In: Proc. 8th IEEE Symp. Structure in Complexity Theory, pp. 102\u2013111 (1993)","key":"18_CR15","DOI":"10.1109\/SCT.1993.336536"},{"unstructured":"Lee, T., Mittal, R., Reichardt, B.W., \u0160palek, R., Szegedy, M.: Quantum query complexity of state conversion. In: Proc. 52nd IEEE FOCS, pp. 344\u2013353 (2011), arXiv:1011.3020","key":"18_CR16"},{"unstructured":"Lee, T., Magniez, F., Santha, M.: A learning graph based quantum query algorithm for finding constant-size subgraphs (2011), arXiv:1109.5135","key":"18_CR17"},{"unstructured":"Magniez, F., Santha, M., Szegedy, M.: Quantum algorithms for the triangle problem. In: Proc. 16th ACM-SIAM Symp. on Discrete Algorithms, SODA (2005), arXiv:quant-ph\/0310134","key":"18_CR18"},{"doi-asserted-by":"crossref","unstructured":"Reingold, O.: Undirected ST-connectivity in log-space. In: Proc. 37th ACM STOC, pp. 376\u2013385 (2005)","key":"18_CR19","DOI":"10.1145\/1060590.1060647"},{"unstructured":"Reichardt, B.W.: Span programs and quantum query complexity: The general adversary bound is nearly tight for every boolean function. Extended Abstract in Proc.\u00a050th IEEE FOCS, pp. 544\u2013551 (2009), arXiv:0904.2759","key":"18_CR20"},{"unstructured":"Reichardt, B.W.: Faster quantum algorithm for evaluating game trees. In: Proc. 22nd ACM-SIAM Symp. on Discrete Algorithms (SODA), pp. 546\u2013559 (2011), arXiv:0907.1623","key":"18_CR21"},{"unstructured":"Reichardt, B.W.: Reflections for quantum query algorithms. In: Proc. 22nd ACM-SIAM Symp. on Discrete Algorithms (SODA), pp. 560\u2013569 (2011), arXiv:1005.1601","key":"18_CR22"},{"unstructured":"Reichardt, B.W.: Span-program-based quantum algorithm for evaluating unbalanced formulas. In: 6th Conf. on Theory of Quantum Computation, Communication and Cryptography, TQC (2011), arXiv:0907.1622","key":"18_CR23"},{"key":"18_CR24","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1016\/j.jctb.2004.08.001","volume":"92","author":"N. Robertson","year":"2004","unstructured":"Robertson, N., Seymour, P.D.: Graph minors XX. Wagner\u2019s conjecture. J. Combin. Theory Ser. B\u00a092, 325\u2013357 (2004)","journal-title":"J. Combin. Theory Ser. B"},{"unstructured":"Reichardt, B.W., \u0160palek, R.: Span-program-based quantum algorithm for evaluating formulas. In: Proc. 40th ACM STOC, pp. 103\u2013112 (2008), arXiv:0710.2630","key":"18_CR25"},{"doi-asserted-by":"crossref","unstructured":"Szegedy, M.: Quantum speed-up of Markov chain based algorithms. In: Proc. 45th IEEE FOCS, pp. 32\u201341 (2004)","key":"18_CR26","DOI":"10.1109\/FOCS.2004.53"},{"doi-asserted-by":"crossref","unstructured":"Williams, V.V., Williams, R.: Subcubic equivalences between path, matrix, and triangle problems. In: Proc. 51st IEEE FOCS, pp. 645\u2013654 (2010)","key":"18_CR27","DOI":"10.1109\/FOCS.2010.67"},{"unstructured":"Zhu, Y.: Quantum query complexity of subgraph containment with constant-sized certificates (2011), arXiv:1109.4165","key":"18_CR28"},{"unstructured":"Zhan, B., Kimmel, S., Hassidim, A.: Super-polynomial quantum speed-ups for boolean evaluation trees with hidden structure (2011), arXiv:1101.0796","key":"18_CR29"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2012"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-33090-2_18.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,7]],"date-time":"2025-04-07T11:35:46Z","timestamp":1744025746000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-33090-2_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642330896","9783642330902"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-33090-2_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}