{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,27]],"date-time":"2025-01-27T05:21:52Z","timestamp":1737955312598,"version":"3.33.0"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2008,1,26]],"date-time":"2008-01-26T00:00:00Z","timestamp":1201305600000},"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-9169-z","type":"journal-article","created":{"date-parts":[[2008,1,25]],"date-time":"2008-01-25T16:00:33Z","timestamp":1201276833000},"page":"557-575","source":"Crossref","is-referenced-by-count":1,"title":["Quantum and Classical Query Complexities of Local Search Are Polynomially Related"],"prefix":"10.1007","volume":"55","author":[{"given":"Miklos","family":"Santha","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mario","family":"Szegedy","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2008,1,26]]},"reference":[{"issue":"4","key":"9169_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":"4","key":"9169_CR2","doi-asserted-by":"crossref","first-page":"595","DOI":"10.1145\/1008731.1008735","volume":"51","author":"S. Aaronson","year":"2004","unstructured":"Aaronson, S., Shi, Y.: Quantum lower bounds for the collision and the element distinctness problems. J. Assoc. Comput. Mach. 51(4), 595\u2013605 (2004)","journal-title":"J. Assoc. Comput. Mach."},{"key":"9169_CR3","volume-title":"Data Structures and Algorithms","author":"A. Aho","year":"1983","unstructured":"Aho, A., Hopcroft, J., Ullman, J.: Data Structures and Algorithms. Addison-Wesley, Reading (1983)"},{"issue":"2","key":"9169_CR4","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."},{"key":"9169_CR5","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. Comput. Syst. Sci. 64, 750\u2013767 (2002)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"9169_CR6","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. Comput. Syst. Sci. 72(2), 220\u2013238 (2006)","journal-title":"J. Comput. Syst. Sci."},{"key":"9169_CR7","doi-asserted-by":"crossref","unstructured":"Barnum, H., Saks, M., Szegedy, M.: Quantum decision trees and semidefinite programming. In: Proc. of the 18th IEEE Conference on Computational Complexity, pp. 179\u2013193 (2003)","DOI":"10.1109\/CCC.2003.1214419"},{"issue":"4","key":"9169_CR8","doi-asserted-by":"crossref","first-page":"778","DOI":"10.1145\/502090.502097","volume":"48","author":"R. Beals","year":"2001","unstructured":"Beals, R., Buhrman, H., Cleve, R., Mosca, M., de Wolf, R.: Quantum lower bounds by polynomials. J.\u00a0Assoc. Comput. Mach. 48(4), 778\u2013797 (2001)","journal-title":"J.\u00a0Assoc. Comput. Mach."},{"issue":"5","key":"9169_CR9","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.: Strength and weaknesses of quantum computing. SIAM J. Comput. 26(5), 1510\u20131523 (1997)","journal-title":"SIAM J. Comput."},{"key":"9169_CR10","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1016\/S0020-0190(99)00069-1","volume":"70","author":"H. Buhrman","year":"1999","unstructured":"Buhrman, H., de Wolf, R.: A lower bound for quantum search of an ordered list. Inf. Process. Lett. 70, 205\u2013209 (1999)","journal-title":"Inf. Process. Lett."},{"key":"9169_CR11","doi-asserted-by":"crossref","unstructured":"Chen, X., Deng, X.: On the complexity of 2D discrete fixed point problem. In: Proc. of the 33rd International Colloquium on Automata, Languages and Programming, pp. 489\u2013500 (2006)","DOI":"10.1007\/11786986_43"},{"key":"9169_CR12","unstructured":"Deutsch, D., Jozsa, R.: Rapid solution of problems by quantum computation. In: Proc. of the Royal Society\u00a0A, vol.\u00a0439 (1985)"},{"issue":"6","key":"9169_CR13","doi-asserted-by":"crossref","first-page":"1310","DOI":"10.1137\/050644719","volume":"35","author":"C. D\u00fcrr","year":"2006","unstructured":"D\u00fcrr, C., Heiligman, M., H\u00f8yer, P., Mhalla, M.: Quantum query complexity of some graph problems. SIAM J. Comput. 35(6), 1310\u20131328 (2006)","journal-title":"SIAM J. Comput."},{"key":"9169_CR14","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1007\/11537311_22","volume-title":"Proc. of the 15th 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 Fundamentals of Computation Theory. LNCS, vol. 3623, pp. 245\u2013257. Springer, Berlin (2005)"},{"key":"9169_CR15","doi-asserted-by":"crossref","unstructured":"Grover, L.: A fast quantum mechanical algorithm for database search. In: Proc. of the 28th ACM Symposium on Theory of Computing, pp. 212\u2013219 (1996)","DOI":"10.1145\/237814.237866"},{"key":"9169_CR16","doi-asserted-by":"crossref","unstructured":"H\u00f8yer, P., Lee, T., \u0160palek, R.: Negative weights make adversaries stronger. In: Proc. of the 39th ACM Symposium on Theory of Computing, pp. 526\u2013535 (2007)","DOI":"10.1145\/1250790.1250867"},{"issue":"4","key":"9169_CR17","doi-asserted-by":"crossref","first-page":"429","DOI":"10.1007\/s00453-002-0976-3","volume":"34","author":"P. H\u00f8yer","year":"2002","unstructured":"H\u00f8yer, P., Neerbek, J., Shi, Y.: Quantum complexities of ordered searching, sorting, and element distinctness. Algorithmica 34(4), 429\u2013448 (2002)","journal-title":"Algorithmica"},{"key":"9169_CR18","doi-asserted-by":"crossref","first-page":"429","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.\u00a0Comput. Syst. Sci. 37, 429\u2013448 (1988)","journal-title":"J.\u00a0Comput. Syst. Sci."},{"key":"9169_CR19","doi-asserted-by":"crossref","unstructured":"Laplante, S., Magniez, F.: Lower bounds for randomized and quantum query complexity using Kolmogorov arguments. In: Proc. of the 19th IEEE Conference on Computational Complexity, pp. 294\u2013304 (2004)","DOI":"10.1109\/CCC.2004.1313852"},{"key":"9169_CR20","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1016\/0166-218X(93)90004-8","volume":"43","author":"D. Llewellyn","year":"1993","unstructured":"Llewellyn, D., Tovey, C.: Dividing and conquering the square. Discrete Appl. Math. 43, 131\u2013153 (1993)","journal-title":"Discrete Appl. Math."},{"key":"9169_CR21","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)","journal-title":"Discrete Appl. Math."},{"key":"9169_CR22","first-page":"93","volume":"46","author":"D. Llewellyn","year":"1993","unstructured":"Llewellyn, D., Tovey, C., Trick, M.: Local optimization on graphs. Erratum 46, 93\u201394 (1993)","journal-title":"Erratum"},{"key":"9169_CR23","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1016\/0304-3975(91)90200-L","volume":"81","author":"N. Megiddo","year":"1991","unstructured":"Megiddo, N., Papadimitriou, C.: On total functions, existence theorems, and computational complexity. Theor. Comp. Sci. 81, 317\u2013324 (1991)","journal-title":"Theor. Comp. Sci."},{"key":"9169_CR24","doi-asserted-by":"crossref","first-page":"96","DOI":"10.4064\/fm-10-1-96-115","volume":"10","author":"K. Menger","year":"1927","unstructured":"Menger, K.: Zur allgemeinen Kurventhoerie. Fundam. Math. 10, 96\u2013115 (1927)","journal-title":"Fundam. Math."},{"issue":"5","key":"9169_CR25","doi-asserted-by":"crossref","first-page":"1474","DOI":"10.1137\/S0097539796298637","volume":"26","author":"D. Simon","year":"1997","unstructured":"Simon, D.: On the power of quantum computation. SIAM J. Comput. 26(5), 1474\u20131783 (1997)","journal-title":"SIAM J. Comput."},{"key":"9169_CR26","unstructured":"\u0160palek, R.: Quantum algorithms, lower bounds, and time-space tradeoffs. Ph.D. Thesis, ILLC Dissertation Series DS-2006-04, Universiteit van Amsterdam (2006)"},{"key":"9169_CR27","doi-asserted-by":"crossref","first-page":"1","DOI":"10.4086\/toc.2006.v002a001","volume":"2","author":"R. \u0160palek","year":"2006","unstructured":"\u0160palek, R., Szegedy, M.: All quantum adversary methods are equivalents. Theory Comput. 2, 1\u201318 (2006)","journal-title":"Theory Comput."},{"key":"9169_CR28","doi-asserted-by":"crossref","unstructured":"Sun, X., Yao, A.: On the quantum query complexity of local search in two and three dimensions. In: Proc. of the 47th IEEE Symposium on Foundations of Computer Science, pp. 429\u2013438 (2006)","DOI":"10.1109\/FOCS.2006.57"},{"key":"9169_CR29","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":"9169_CR30","doi-asserted-by":"crossref","first-page":"2746","DOI":"10.1103\/PhysRevA.60.2746","volume":"60","author":"C. Zalka","year":"1999","unstructured":"Zalka, C.: Grover\u2019s quantum searching algorithm is optimal. Phys. Rev.\u00a0A 60, 2746\u20132751 (1999)","journal-title":"Phys. Rev.\u00a0A"},{"key":"9169_CR31","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. Comp. Sci. 339, 241\u2013256 (2005)","journal-title":"Theor. Comp. Sci."},{"key":"9169_CR32","doi-asserted-by":"crossref","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 (2006)","DOI":"10.1145\/1132516.1132605"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-008-9169-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-008-9169-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-008-9169-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,26]],"date-time":"2025-01-26T08:15:29Z","timestamp":1737879329000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-008-9169-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,1,26]]},"references-count":32,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2009,11]]}},"alternative-id":["9169"],"URL":"https:\/\/doi.org\/10.1007\/s00453-008-9169-z","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2008,1,26]]}}}