{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,29]],"date-time":"2022-03-29T03:16:38Z","timestamp":1648523798815},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2009,2,25]],"date-time":"2009-02-25T00:00:00Z","timestamp":1235520000000},"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":[[2010,3]]},"DOI":"10.1007\/s00453-009-9289-0","type":"journal-article","created":{"date-parts":[[2009,2,24]],"date-time":"2009-02-24T16:48:18Z","timestamp":1235494098000},"page":"364-382","source":"Crossref","is-referenced-by-count":0,"title":["Quantum Separation of Local Search and Fixed Point Computation"],"prefix":"10.1007","volume":"56","author":[{"given":"Xi","family":"Chen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiaoming","family":"Sun","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shang-Hua","family":"Teng","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2009,2,25]]},"reference":[{"key":"9289_CR1","doi-asserted-by":"crossref","unstructured":"Chen, X., Teng, S.H.: Paths beyond local search: a tight bound for randomized fixed-point computation. In: Proceedings of the 48th FOCS, pp. 124\u2013134 (2007)","DOI":"10.1109\/FOCS.2007.14"},{"issue":"1","key":"9289_CR2","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1073\/pnas.36.1.48","volume":"36","author":"J. Nash","year":"1950","unstructured":"Nash, J.: Equilibrium point in n-person games. Proc. Natl. Acad. USA 36(1), 48\u201349 (1950)","journal-title":"Proc. Natl. Acad. USA"},{"issue":"3","key":"9289_CR3","doi-asserted-by":"crossref","first-page":"265","DOI":"10.2307\/1907353","volume":"22","author":"K. Arrow","year":"1954","unstructured":"Arrow, K., Debreu, G.: Existence of an equilibrium for a competitive economy. Econometrica 22(3), 265\u2013290 (1954)","journal-title":"Econometrica"},{"key":"9289_CR4","doi-asserted-by":"crossref","first-page":"997","DOI":"10.1137\/0115116","volume":"15","author":"H. Scarf","year":"1967","unstructured":"Scarf, H.: The approximation of fixed points of a continuous mapping. SIAM J. Appl. Math. 15, 997\u20131007 (1967)","journal-title":"SIAM J. Appl. Math."},{"key":"9289_CR5","volume-title":"Ten Economic Studies in the Tradition of Irving Fisher","author":"H. Scarf","year":"1967","unstructured":"Scarf, H.: On the computation of equilibrium prices. In: Fellner, W. (ed.) Ten Economic Studies in the Tradition of Irving Fisher. Wiley, New York (1967)"},{"key":"9289_CR6","doi-asserted-by":"crossref","unstructured":"Papadimitriou, C.: On inefficient proofs of existence and complexity classes. In: Proceedings of the 4th Czechoslovakian Symposium on Combinatorics (1991)","DOI":"10.1016\/S0167-5060(08)70637-X"},{"key":"9289_CR7","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1016\/0885-064X(89)90017-4","volume":"5","author":"M. Hirsch","year":"1989","unstructured":"Hirsch, M., Papadimitriou, C., Vavasis, S.: Exponential lower bounds for finding Brouwer fixed points. J. Complex. 5, 379\u2013416 (1989)","journal-title":"J. Complex."},{"issue":"2","key":"9289_CR8","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1016\/S0022-0000(03)00011-4","volume":"67","author":"X. Deng","year":"2003","unstructured":"Deng, X., Papadimitriou, C., Safra, S.: On the complexity of price equilibria. J. Comput. Syst. Sci. 67(2), 311\u2013324 (2003)","journal-title":"J. Comput. Syst. Sci."},{"key":"9289_CR9","doi-asserted-by":"crossref","first-page":"1030","DOI":"10.1016\/j.jmateco.2005.03.001","volume":"41","author":"T. Iimura","year":"2005","unstructured":"Iimura, T., Murota, K., Tamura, A.: Discrete fixed point theorem reconsidered. J. Math. Econ. 41, 1030\u20131036 (2005)","journal-title":"J. Math. Econ."},{"issue":"2","key":"9289_CR10","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":"9289_CR11","doi-asserted-by":"crossref","unstructured":"Friedl, K., Ivanyos, G., Santha, M., Verhoeven, F.: On the black-box complexity of Sperner\u2019s lemma. In: Proceedings of the 15th FCT, pp. 245\u2013257 (2005)","DOI":"10.1007\/11537311_22"},{"key":"9289_CR12","doi-asserted-by":"crossref","unstructured":"Aaronson, S.: Lower bounds for local search by quantum arguments. In: Proceedings of the 36th STOC, pp. 465\u2013474 (2004)","DOI":"10.1145\/1007352.1007358"},{"key":"9289_CR13","doi-asserted-by":"crossref","unstructured":"Ambainis, A.: Polynomial degree vs. quantum query complexity. In: Proceedings of the 44th FOCS, pp. 230\u2013239 (2003)","DOI":"10.1109\/SFCS.2003.1238197"},{"issue":"2\u20133","key":"9289_CR14","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(2\u20133), 241\u2013256 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"9289_CR15","doi-asserted-by":"crossref","unstructured":"Zhang, S.: New upper and lower bounds for randomized and quantum local search. In: Proceedings of the 38th STOC, pp. 634\u2013643 (2006)","DOI":"10.1145\/1132516.1132605"},{"key":"9289_CR16","doi-asserted-by":"crossref","unstructured":"Sun, X., Yao, A.C.: On the quantum query complexity of local search in two and three dimensions. In: Proceedings of the 47th FOCS, pp. 429\u2013438 (2006)","DOI":"10.1109\/FOCS.2006.57"},{"key":"9289_CR17","doi-asserted-by":"crossref","unstructured":"Chen, X., Deng, X.: On algorithms for discrete and approximate Brouwer fixed points. In: Proceedings of the 37th STOC, pp. 323\u2013330 (2005)","DOI":"10.1145\/1060590.1060638"},{"key":"9289_CR18","doi-asserted-by":"crossref","unstructured":"Santha, M., Szegedy, M.: Quantum and classical query complexities of local search are polynomially related. In: Proceedings of the 36th STOC, pp. 494\u2013501 (2004)","DOI":"10.1145\/1007352.1007427"},{"key":"9289_CR19","doi-asserted-by":"crossref","unstructured":"Barnum, H., Saks, M., Szegedy, M.: Quantum query complexity and semi-definite programming. In: Proceedings of the 18th CCC, pp. 179\u2013193 (2003)","DOI":"10.1109\/CCC.2003.1214419"},{"key":"9289_CR20","doi-asserted-by":"crossref","unstructured":"Laplante, S., Magniez, F.: Lower bounds for randomized and quantum query complexity using Kolmogorov arguments. In: Proceedings of the 19th CCC, pp. 294\u2013304 (2004)","DOI":"10.1109\/CCC.2004.1313852"},{"key":"9289_CR21","doi-asserted-by":"crossref","unstructured":"Spalek, R., Szegedy, M.: All quantum adversary methods are equivalent. In: Proceedings of the 32nd ICALP, pp. 1299\u20131311 (2005)","DOI":"10.1007\/11523468_105"},{"key":"9289_CR22","doi-asserted-by":"crossref","unstructured":"H\u00f8yer, P., Lee, T., Spalek, R.: Negative weights make adversaries stronger. In: Proceedings of the 39th STOC, pp. 526\u2013535 (2007)","DOI":"10.1145\/1250790.1250867"},{"issue":"4","key":"9289_CR23","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. ACM 48(4), 778\u2013797 (2001)","journal-title":"J. ACM"},{"key":"9289_CR24","doi-asserted-by":"crossref","unstructured":"Ambainis, A.: Quantum lower bounds by quantum arguments. In: Proceedings of the 32nd FOCS, pp.\u00a0636\u2013643 (2000)","DOI":"10.1145\/335305.335394"},{"key":"9289_CR25","doi-asserted-by":"crossref","unstructured":"Grover, L.: A fast quantum mechanical algorithm for database search. In: Proceedings of the 28th STOC, pp. 212\u2013219 (1996)","DOI":"10.1145\/237814.237866"},{"key":"9289_CR26","doi-asserted-by":"crossref","unstructured":"Buhrman, H., Cleve, R., Wigderson, A.: Quantum vs. classical communication and computation. In: Proceedings of the 30th STOC, pp. 63\u201368 (1998)","DOI":"10.1145\/276698.276713"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-009-9289-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-009-9289-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-009-9289-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T09:45:03Z","timestamp":1559123103000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-009-9289-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,2,25]]},"references-count":26,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2010,3]]}},"alternative-id":["9289"],"URL":"https:\/\/doi.org\/10.1007\/s00453-009-9289-0","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,2,25]]}}}