{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T19:01:35Z","timestamp":1750705295403,"version":"3.40.3"},"publisher-location":"Cham","reference-count":12,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319298160"},{"type":"electronic","value":"9783319298177"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-29817-7_4","type":"book-chapter","created":{"date-parts":[[2016,2,3]],"date-time":"2016-02-03T00:46:18Z","timestamp":1454460378000},"page":"35-41","source":"Crossref","is-referenced-by-count":2,"title":["Span-Program-Based Quantum Algorithms for Graph Bipartiteness and Connectivity"],"prefix":"10.1007","author":[{"given":"Agnis","family":"\u0100ri\u0146\u0161","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"4_CR1","unstructured":"Ambainis, A., Balodis, K., Iraids, J., Ozols, R., Smotrovs, J.: Parameterized quantum query complexity of graph collision. CoRR abs\/1305.1021 (2013). \n                    http:\/\/arxiv.org\/abs\/1305.1021"},{"key":"4_CR2","unstructured":"Belovs, A.: Span-program-based quantum algorithm for the rank problem. CoRR abs\/1103.0842 (2011). \n                    http:\/\/arxiv.org\/abs\/1103.0842"},{"key":"4_CR3","unstructured":"Belovs, A.: Learning-graph-based quantum algorithm for k-distinctness. In: IEEE 53rd Annual Symposium on Foundations of Computer Science (FOCS), pp. 207\u2013216. IEEE (2012). \n                    http:\/\/ieeexplore.ieee.org\/xpls\/abs_all.jsp?arnumber=6375298"},{"key":"4_CR4","unstructured":"Belovs, A.: Span programs for functions with constant-sized 1-certificates. In: Proceedings of the 44th Symposium on Theory of Computing, pp. 77\u201384. ACM (2012). \n                    http:\/\/dl.acm.org\/citation.cfm?id=2213985"},{"key":"4_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/978-3-642-33090-2_18","volume-title":"Algorithms \u2013 ESA 2012","author":"A Belovs","year":"2012","unstructured":"Belovs, A., Reichardt, B.W.: Span programs and quantum algorithms for st-connectivity and claw detection. In: Epstein, L., Ferragina, P. (eds.) ESA 2012. LNCS, vol. 7501, pp. 193\u2013204. Springer, Heidelberg (2012). \n                    http:\/\/dx.doi.org\/10.1007\/978-3-642-33090-2_18"},{"key":"4_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"140","DOI":"10.1007\/978-3-540-24618-3_11","volume-title":"SOFSEM 2004: Theory and Practice of Computer Science","author":"A Berzina","year":"2004","unstructured":"Berzina, A., Dubrovsky, A., Freivalds, R., Lace, L., Scegulnaja, O.: Quantum query complexity for some graph problems. In: Van Emde Boas, P., Pokorn\u00fd, J., Bielikov\u00e1, M., \u0160tuller, J. (eds.) SOFSEM 2004. LNCS, vol. 2932, pp. 140\u2013150. Springer, Heidelberg (2004). \n                    http:\/\/dx.doi.org\/10.1007\/978-3-540-24618-3_11"},{"key":"4_CR7","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. 3142, pp. 481\u2013493. Springer, Heidelberg (2004). \n                    http:\/\/dx.doi.org\/10.1007\/978-3-540-27836-8_42"},{"issue":"8","key":"4_CR8","first-page":"834","volume":"8","author":"B Furrow","year":"2008","unstructured":"Furrow, B.: A panoply of quantum algorithms. Quantum Info. Comput. 8(8), 834\u2013859 (2008). \n                    http:\/\/dl.acm.org\/citation.cfm?id=2017011.2017022","journal-title":"Quantum Info. Comput."},{"key":"4_CR9","unstructured":"Karchmer, M., Wigderson, A.: On span programs. In: Proceedings of the Eighth Annual Structure in Complexity Theory Conference, pp. 102\u2013111. IEEE (1993). \n                    http:\/\/ieeexplore.ieee.org\/xpls\/abs_all.jsp?arnumber=336536"},{"key":"4_CR10","unstructured":"Reichardt, B.W.: Span programs and quantum query complexity: the general adversary bound is nearly tight for every boolean function. In: 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 544\u2013551. IEEE (2009). \n                    http:\/\/ieeexplore.ieee.org\/xpls\/abs_all.jsp?arnumber=5438598"},{"key":"4_CR11","unstructured":"Reichardt, B.W.: Reflections for quantum query algorithms. In: Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 560\u2013569. SIAM (2011). \n                    http:\/\/dl.acm.org\/citation.cfm?id=2133080"},{"key":"4_CR12","unstructured":"Reichardt, B.W., Spalek, R.: Span-program-based quantum algorithm for evaluating formulas. In: Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, STOC 2008, pp. 103\u2013112. ACM, New York (2008). \n                    http:\/\/doi.acm.org\/10.1145\/1374376.1374394"}],"container-title":["Lecture Notes in Computer Science","Mathematical and Engineering Methods in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-29817-7_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,1]],"date-time":"2019-06-01T09:02:48Z","timestamp":1559379768000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-29817-7_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319298160","9783319298177"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-29817-7_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}