{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,2]],"date-time":"2026-10-02T02:27:20Z","timestamp":1790908040084,"version":"4.1.0"},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2008,1,29]],"date-time":"2008-01-29T00:00:00Z","timestamp":1201564800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2009,11]]},"DOI":"10.1007\/s00453-008-9170-6","type":"journal-article","created":{"date-parts":[[2008,1,28]],"date-time":"2008-01-28T20:17:00Z","timestamp":1201551420000},"page":"576-600","source":"Crossref","is-referenced-by-count":6,"title":["On the Quantum Query Complexity of Local Search in\u00a0Two and Three Dimensions"],"prefix":"10.1007","volume":"55","author":[{"given":"Xiaoming","family":"Sun","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andrew Chi-Chih","family":"Yao","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2008,1,29]]},"reference":[{"issue":"4","key":"9170_CR1","doi-asserted-by":"crossref","first-page":"804","DOI":"10.1137\/S0097539704447237","volume":"35","author":"S. Aaronson","year":"2006","unstructured":"Aaronson, S.: Lower bounds for local search by quantum arguments. SIAM J. Comput. 35(4), 804\u2013824 (2006)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"9170_CR2","doi-asserted-by":"crossref","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. Ann. Probab. 11(2), 403\u2013413 (1983)","journal-title":"Ann. Probab."},{"issue":"4","key":"9170_CR3","doi-asserted-by":"crossref","first-page":"750","DOI":"10.1006\/jcss.2002.1826","volume":"64","author":"A. Ambainis","year":"2002","unstructured":"Ambainis, A.: Quantum lower bounds by quantum arguments. J.\u00a0Comput. Syst. Sci. 64(4), 750\u2013767 (2002)","journal-title":"J.\u00a0Comput. Syst. Sci."},{"issue":"2","key":"9170_CR4","doi-asserted-by":"crossref","first-page":"220","DOI":"10.1016\/j.jcss.2005.06.006","volume":"72","author":"A. Ambainis","year":"2006","unstructured":"Ambainis, A.: Polynomial degree vs. quantum query complexity. J.\u00a0Comput. Syst. Sci. 72(2), 220\u2013238 (2006)","journal-title":"J.\u00a0Comput. Syst. Sci."},{"issue":"5","key":"9170_CR5","doi-asserted-by":"crossref","first-page":"1510","DOI":"10.1137\/S0097539796300933","volume":"26","author":"C. Bennett","year":"1997","unstructured":"Bennett, C., Bernstein, E., Brassard, G., Vazirani, U.: Strengths and weaknesses of quantum computation. SIAM J. Comput. 26(5), 1510\u20131523 (1997)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9170_CR6","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1007\/BF02566968","volume":"37","author":"R.C. Bose","year":"1962","unstructured":"Bose, R.C., Chowla, S.: Theorems in the additive theory of numbers. Comment. Math. Helv. 37(1), 141\u2013147 (1962)","journal-title":"Comment. Math. Helv."},{"key":"9170_CR7","first-page":"323","volume-title":"Proc. of the 37th Annual ACM Symposium on Theory of Computing","author":"X. Chen","year":"2005","unstructured":"Chen, X., Deng, X.: On algorithms for discrete and approximate brouwer fixed points. In: Proc. of the 37th Annual ACM Symposium on Theory of Computing, pp. 323\u2013330. Assoc. Comput. Mach., New York (2005)"},{"key":"9170_CR8","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF02392223","volume":"77","author":"C.G. Esseen","year":"1945","unstructured":"Esseen, C.G.: Fourier analysis of distribution functions. Acta Math. 77, 1\u2013125 (1945)","journal-title":"Acta Math."},{"key":"9170_CR9","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1007\/11537311_22","volume-title":"Proc. of the 15th International Symposium on Fundamentals of Computation Theory","author":"K. Friedl","year":"2005","unstructured":"Friedl, K., Ivanyos, G., Santha, M., Verhoeven, Y.: On the black-box complexity of Sperner\u2019s Lemma. In: Proc. of the 15th International Symposium on Fundamentals of Computation Theory, pp. 245\u2013257. Springer, Berlin (2005)"},{"issue":"3\u20134","key":"9170_CR10","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1007\/BF02018403","volume":"8","author":"G. Hal\u00e1sz","year":"1977","unstructured":"Hal\u00e1sz, G.: Estimates for the concentration function of combinatorial number theory and probability. Period. Math. Hung. 8(3\u20134), 197\u2013211 (1977)","journal-title":"Period. Math. Hung."},{"key":"9170_CR11","volume-title":"Sequences","author":"H. Halberstam","year":"1966","unstructured":"Halberstam, H., Roth, K.F.: Sequences. Oxford University Press, Oxford (1966)"},{"issue":"1","key":"9170_CR12","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1016\/0022-0000(88)90046-3","volume":"37","author":"D. Johnson","year":"1988","unstructured":"Johnson, D., Papadimitriou, C., Yannakakis, M.: How easy is local search? J. Comput. Syst. Sci. 37(1), 79\u2013100 (1988)","journal-title":"J. Comput. Syst. Sci."},{"key":"9170_CR13","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1016\/0166-218X(89)90025-5","volume":"23","author":"D. Llewellyn","year":"1989","unstructured":"Llewellyn, D., Tovey, C., Trick, M.: Local optimization on graphs. Discrete Appl. Math. 23, 157\u2013178 (1989). Erratum: 46, 93\u201394 (1993)","journal-title":"Discrete Appl. Math."},{"key":"9170_CR14","first-page":"494","volume-title":"Proc. of the 36th 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: Proc. of the 36th Annual ACM Symposium on Theory of Computing, pp. 494\u2013501. Assoc. Comput. Mach., New York (2004)"},{"key":"9170_CR15","doi-asserted-by":"crossref","first-page":"205","DOI":"10.4064\/aa-11-2-205-208","volume":"11","author":"A. S\u00e1rk\u00f6zy","year":"1965","unstructured":"S\u00e1rk\u00f6zy, A., Szemer\u00e9di, E.: \u00dcber ein Problem von Erd\u00f6s und Moser. Acta Arith. 11, 205\u2013208 (1965)","journal-title":"Acta Arith."},{"key":"9170_CR16","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1016\/j.ipl.2005.11.004","volume":"97","author":"Y. Verhoeven","year":"2006","unstructured":"Verhoeven, Y.: Enhanced algorithms for local search. Inf. Process. Lett. 97, 171\u2013176 (2006)","journal-title":"Inf. Process. Lett."},{"key":"9170_CR17","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1016\/j.tcs.2005.01.019","volume":"339","author":"S. Zhang","year":"2005","unstructured":"Zhang, S.: On the power of Ambainis\u2019s lower bounds. Theor. Comput. Sci. 339, 241\u2013256 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"9170_CR18","first-page":"634","volume-title":"Proc. of the 38th 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: Proc. of the 38th ACM Symposium on Theory of Computing, pp. 634\u2013643. Assoc. Comput. Mach., New York (2006)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-008-9170-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-008-9170-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-008-9170-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:45:01Z","timestamp":1559137501000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-008-9170-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,1,29]]},"references-count":18,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2009,11]]}},"alternative-id":["9170"],"URL":"https:\/\/doi.org\/10.1007\/s00453-008-9170-6","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,1,29]]}}}