{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T06:31:14Z","timestamp":1725517874300},"publisher-location":"Berlin, Heidelberg","reference-count":11,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540853626"},{"type":"electronic","value":"9783540853633"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-85363-3_31","type":"book-chapter","created":{"date-parts":[[2008,8,27]],"date-time":"2008-08-27T19:29:28Z","timestamp":1219865368000},"page":"385-401","source":"Crossref","is-referenced-by-count":21,"title":["Quantum and Randomized Lower Bounds for Local Search on Vertex-Transitive Graphs"],"prefix":"10.1007","author":[{"given":"Hang","family":"Dinh","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexander","family":"Russell","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"31_CR1","unstructured":"Aardal, K., van Hoesel, S., Lenstra, J.K., Stougie, L.: A decade of combinatorial optimization. In: CWI Tracts, vol.\u00a0122, pp. 5\u201314 (1997)"},{"key":"31_CR2","doi-asserted-by":"crossref","unstructured":"Aaronson, S.: Lower bounds for local search by quantum arguments. In: STOC 2004: Proceedings of the 36th Annual ACM Symposium on Theory of Computing (2004)","DOI":"10.1145\/1007352.1007358"},{"issue":"2","key":"31_CR3","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1214\/aop\/1176993605","volume":"11","author":"D. Aldous","year":"1983","unstructured":"Aldous, D.: Minimization algorithms and random walk on the d-cube. Annals of Probability\u00a011(2), 403\u2013413 (1983)","journal-title":"Annals of Probability"},{"key":"31_CR4","doi-asserted-by":"crossref","unstructured":"Ambainis, A.: Quantum lower bounds by quantum arguments. In: STOC 2000: Proceedings of the thirty-second annual ACM symposium on Theory of computing (2000)","DOI":"10.1145\/335305.335394"},{"key":"31_CR5","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1145\/103418.103440","volume-title":"STOC 1991: Proceedings of the twenty-third annual ACM symposium on Theory of computing","author":"L. Babai","year":"1991","unstructured":"Babai, L.: Local expansion of vertex-transitive graphs and random generation in finite groups. In: STOC 1991: Proceedings of the twenty-third annual ACM symposium on Theory of computing, pp. 164\u2013174. ACM, New York (1991)"},{"issue":"2","key":"31_CR6","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1016\/0166-218X(89)90025-5","volume":"23","author":"D.C. Llewellyn","year":"1989","unstructured":"Llewellyn, D.C., Tovey, C., Trick, M.: Local optimization on graphs. Discrete Appl. Math.\u00a023(2), 157\u2013178 (1989)","journal-title":"Discrete Appl. Math."},{"key":"31_CR7","doi-asserted-by":"crossref","unstructured":"Mohar, B., Thomassen, C.: Graphs on Surfaces. The Johns Hopkins University Press (2001)","DOI":"10.56021\/9780801866890"},{"key":"31_CR8","doi-asserted-by":"publisher","first-page":"494","DOI":"10.1145\/1007352.1007427","volume-title":"STOC 2004: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing","author":"M. Santha","year":"2004","unstructured":"Santha, M., Szegedy, M.: Quantum and classical query complexities of local search are polynomially related. In: STOC 2004: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, pp. 494\u2013501. ACM, New York (2004)"},{"key":"31_CR9","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1109\/FOCS.2006.57","volume-title":"FOCS 2006: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science","author":"X. Sun","year":"2006","unstructured":"Sun, X., Yao, A.C.: On the quantum query complexity of local search in two and three dimensions. In: FOCS 2006: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, Washington, DC, USA, pp. 429\u2013438. IEEE Computer Society, Los Alamitos (2006)"},{"issue":"5","key":"31_CR10","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/j.ipl.2005.11.004","volume":"97","author":"Y.F. Verhoeven","year":"2006","unstructured":"Verhoeven, Y.F.: Enhanced algorithms for local search. Inf. Process. Lett.\u00a097(5), 171\u2013176 (2006)","journal-title":"Inf. Process. Lett."},{"key":"31_CR11","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1145\/1132516.1132605","volume-title":"STOC 2006: Proceedings of the thirty-eighth annual ACM symposium on Theory of computing","author":"S. Zhang","year":"2006","unstructured":"Zhang, S.: New upper and lower bounds for randomized and quantum local search. In: STOC 2006: Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, pp. 634\u2013643. ACM, New York (2006)"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-85363-3_31.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,19]],"date-time":"2023-05-19T19:23:29Z","timestamp":1684524209000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-85363-3_31"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540853626","9783540853633"],"references-count":11,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-85363-3_31","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}