乐胖代购免代理版

{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,30]],"date-time":"2025-01-30T16:10:13Z","timestamp":1738253413407,"version":"3.35.0"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2008,6,5]],"date-time":"2008-06-05T00:00:00Z","timestamp":1212624000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2009,10]]},"DOI":"10.1007\/s00224-008-9121-2","type":"journal-article","created":{"date-parts":[[2008,6,4]],"date-time":"2008-06-04T16:43:26Z","timestamp":1212597806000},"page":"629-646","source":"Crossref","is-referenced-by-count":2,"title":["On the Black-Box Complexity of Sperner\u2019s\u00a0Lemma"],"prefix":"10.1007","volume":"45","author":[{"given":"Katalin","family":"Friedl","sequence":"first","affiliation":[]},{"given":"G\u00e1bor","family":"Ivanyos","sequence":"additional","affiliation":[]},{"given":"Miklos","family":"Santha","sequence":"additional","affiliation":[]},{"given":"Yves F.","family":"Verhoeven","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2008,6,5]]},"reference":[{"issue":"4","key":"9121_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":"9121_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. ACM 51(4), 595\u2013605 (2004)","journal-title":"J. ACM"},{"key":"9121_CR3","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, 220\u2013238 (2006)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"9121_CR4","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"},{"issue":"1","key":"9121_CR5","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1006\/jcss.1998.1575","volume":"57","author":"P. Beame","year":"1998","unstructured":"Beame, P., Cook, S., Edmonds, J., Impagliazzo, R., Pitassi, T.: The relative complexity of NP search problems. J. Comput. Syst. Sci. 57(1), 3\u201319 (1998)","journal-title":"J. Comput. Syst. Sci."},{"issue":"5","key":"9121_CR6","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."},{"issue":"5","key":"9121_CR7","doi-asserted-by":"crossref","first-page":"490","DOI":"10.1002\/mana.200310373","volume":"279","author":"E. Bloch","year":"2006","unstructured":"Bloch, E.: Mod 2 degree and a generalized No Retraction Theorem. Math. Nachr. 279(5), 490\u2013494 (2006)","journal-title":"Math. Nachr."},{"key":"9121_CR8","doi-asserted-by":"crossref","unstructured":"Buresh-Oppenheim, J., Morioka, T.: Relativized NP search problems and propositional proof systems. In: 19th Conference on Computational Complexity, pp. 54\u201367 (2004)","DOI":"10.1109\/CCC.2004.1313795"},{"key":"9121_CR9","doi-asserted-by":"crossref","unstructured":"Chen, X., Deng, X.: On the complexity of 2D discrete fixed point problem. In: 33rd International Colloquium on Automata, Languages and Programming, pp. 489\u2013500 (2006)","DOI":"10.1007\/11786986_43"},{"key":"9121_CR10","doi-asserted-by":"crossref","unstructured":"Chen, X., Teng, S.: Paths beyond local search: a nearly tight bound for randomized fixed-point computation. In: 48th Annual Symposium on Foundations of Computer Science, pp.\u00a0124\u2013134 (2007)","DOI":"10.1109\/FOCS.2007.14"},{"key":"9121_CR11","doi-asserted-by":"crossref","unstructured":"Chen, X., Sun, X., Teng, S.: Quantum separation of local search and fixed point computation. In: 14th Annual International Computing and Combinatorics Conference (2008, to appear)","DOI":"10.1007\/978-3-540-69733-6_18"},{"issue":"2","key":"9121_CR12","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1007\/s000370050008","volume":"7","author":"P. Crescenzi","year":"1998","unstructured":"Crescenzi, P., Silvestri, R.: Sperner\u2019s lemma and robust machines. Conf. Comput. Complex. 7(2), 163\u2013173 (1998)","journal-title":"Conf. Comput. Complex."},{"key":"9121_CR13","doi-asserted-by":"crossref","first-page":"553","DOI":"10.1098\/rspa.1992.0167","volume":"439","author":"D. Deutsch","year":"1992","unstructured":"Deutsch, D., Jozsa, R.: Rapid solution of problems by quantum computation. Proc. R. Soc. A 439, 553\u2013558 (1992)","journal-title":"Proc. R. Soc. A"},{"key":"9121_CR14","doi-asserted-by":"crossref","first-page":"588","DOI":"10.1016\/S0021-9800(67)80063-2","volume":"2","author":"K. Fan","year":"1967","unstructured":"Fan, K.: Simplicial maps from an orientable n-pseudomanifold into S m with the octahedral triangulation. J. Comb. Theory 2, 588\u2013602 (1967)","journal-title":"J. Comb. Theory"},{"key":"9121_CR15","doi-asserted-by":"crossref","unstructured":"Friedl, K., Ivanyos, G., Santha, M., Verhoeven, Y.: On the black-box complexity of Sperner\u2019s Lemma. In: 15th International Symposium on Fundamentals of Computation Theory. LNCS vol. 3623, pp. 245\u2013257 (2005)","DOI":"10.1007\/11537311_22"},{"key":"9121_CR16","doi-asserted-by":"crossref","unstructured":"Friedl, K., Ivanyos, G., Santha, M., Verhoeven, Y.: Locally 2-dimensional Sperner problem complete for the Polynomial Parity Argument classes. In: 6th Italian Conference on Algorithms and Complexity. LNCS vol. 3998, pp. 380\u2013391 (2006)","DOI":"10.1007\/11758471_36"},{"issue":"3","key":"9121_CR17","doi-asserted-by":"crossref","first-page":"391","DOI":"10.1016\/0196-6774(84)90019-1","volume":"5","author":"J. Gilbert","year":"1984","unstructured":"Gilbert, J., Hutchinson, J., Tarjan, R.: A separator theorem for graphs of bounded genus. J. Algorithms 5(3), 391\u2013407 (1984)","journal-title":"J. Algorithms"},{"issue":"5\u20136","key":"9121_CR18","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1016\/S0020-0190(00)00152-6","volume":"77","author":"M. Grigni","year":"2001","unstructured":"Grigni, M.: A Sperner Lemma complete for PPA. Inf. Process. Lett. 77(5\u20136), 255\u2013259 (2001)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"9121_CR19","doi-asserted-by":"crossref","first-page":"46","DOI":"10.1137\/050639090","volume":"38","author":"S. Laplante","year":"2008","unstructured":"Laplante, S., Magniez, F.: Lower bounds for randomized and quantum query complexity using Kolmogorov arguments. SIAM J. Comput. 38(1), 46\u201362 (2008). 19th Conference on Computational Complexity, pp.\u00a0294\u2013304 (2004)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"9121_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(2), 131\u2013153 (1993)","journal-title":"Discrete Appl. Math."},{"issue":"2","key":"9121_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(2), 157\u2013178 (1989)","journal-title":"Discrete Appl. Math."},{"key":"9121_CR22","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. Comput. Sci. 81, 317\u2013324 (1991)","journal-title":"Theor. Comput. Sci."},{"key":"9121_CR23","doi-asserted-by":"crossref","unstructured":"Papadimitriou, C.: On graph-theoretic lemmata and complexity classes. In: 31st Foundations of Computer Science, pp. 794\u2013801 (1990)","DOI":"10.1109\/FSCS.1990.89602"},{"issue":"3","key":"9121_CR24","doi-asserted-by":"crossref","first-page":"498","DOI":"10.1016\/S0022-0000(05)80063-7","volume":"48","author":"C. Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.: On the complexity of the parity argument and other inefficient proofs of existence. J. Comput. System Sci. 48(3), 498\u2013532 (1994)","journal-title":"J. Comput. System Sci."},{"key":"9121_CR25","doi-asserted-by":"crossref","unstructured":"Santha, M., Szegedy, M.: Quantum and classical query complexities of local search are polynomially related. In: 36th Symposium on Theory of Computing, pp. 494\u2013501 (2004). To appear in Algorithmica","DOI":"10.1145\/1007352.1007427"},{"issue":"5","key":"9121_CR26","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":"9121_CR27","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1007\/BF02940617","volume":"6","author":"E. Sperner","year":"1928","unstructured":"Sperner, E.: Neuer Beweis f\u00fcr die Invarianz der Dimensionzahl und des Gebietes. Abh. Math. Semin. Hamb. Univ. 6, 265\u2013272 (1928)","journal-title":"Abh. Math. Semin. Hamb. Univ."},{"issue":"1","key":"9121_CR28","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 equivalent. Theory Comput. 2(1), 1\u201318 (2006)","journal-title":"Theory Comput."},{"key":"9121_CR29","unstructured":"Taylor, L.: Sperner\u2019s Lemma, Brouwer\u2019s Fixed Point Theorem, The Fundamental Theorem of Algebra. http:\/\/www.cs.csubak.edu\/~larry\/math\/sperner.pdf"},{"key":"9121_CR30","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1016\/S0167-5060(08)70511-9","volume":"3","author":"A. Thomason","year":"1978","unstructured":"Thomason, A.: Hamilton cycles and uniquely edge colourable graphs. Ann. Discrete Math. 3, 259\u2013268 (1978)","journal-title":"Ann. Discrete Math."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-008-9121-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-008-9121-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-008-9121-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,30]],"date-time":"2025-01-30T15:29:02Z","timestamp":1738250942000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-008-9121-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,6,5]]},"references-count":30,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2009,10]]}},"alternative-id":["9121"],"URL":"https:\/\/doi.org\/10.1007\/s00224-008-9121-2","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2008,6,5]]}}}