{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T18:17:45Z","timestamp":1725560265568},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540281931"},{"type":"electronic","value":"9783540318736"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11537311_22","type":"book-chapter","created":{"date-parts":[[2005,9,27]],"date-time":"2005-09-27T10:00:06Z","timestamp":1127815206000},"page":"245-257","source":"Crossref","is-referenced-by-count":16,"title":["On the Black-Box Complexity of Sperner\u2019s Lemma"],"prefix":"10.1007","author":[{"given":"Katalin","family":"Friedl","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"G\u00e1bor","family":"Ivanyos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Miklos","family":"Santha","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yves F.","family":"Verhoeven","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"22_CR1","doi-asserted-by":"crossref","unstructured":"Aaronson, S.: Quantum lower bound for the collision problem. In: 34th STOC, pp. 635\u2013642 (2002)","DOI":"10.1145\/509907.509999"},{"key":"22_CR2","doi-asserted-by":"crossref","unstructured":"Aaronson, S.: Lower bounds for local search by quantum arguments. In: 36th STOC, pp. 465\u2013474 (2004)","DOI":"10.1145\/1007352.1007358"},{"key":"22_CR3","doi-asserted-by":"crossref","unstructured":"Ambainis, A.: Polynomial degree vs. quantum query complexity. In: 44th FOCS, pp. 230\u2013239 (2003)","DOI":"10.1109\/SFCS.2003.1238197"},{"issue":"48","key":"22_CR4","doi-asserted-by":"publisher","first-page":"778","DOI":"10.1145\/502090.502097","volume":"4","author":"R. Beals","year":"2001","unstructured":"Beals, R., Buhrman, H., Cleve, R., Mosca, M., de Wolf, R.: Quantum lower bounds by polynomials. J. of the ACM\u00a04(48), 778\u2013797 (2001)","journal-title":"J. of the ACM"},{"issue":"1","key":"22_CR5","doi-asserted-by":"publisher","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. System Sci.\u00a057(1), 3\u201319 (1998)","journal-title":"J. Comput. System Sci."},{"issue":"5","key":"22_CR6","doi-asserted-by":"publisher","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. on Computing\u00a026(5), 1510\u20131523 (1997)","journal-title":"SIAM J. on Computing"},{"key":"22_CR7","unstructured":"Bloch, E.: Mod 2 degree and a generalized no retraction Theorem. To appear in Mathematische Nachrichten"},{"key":"22_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"},{"issue":"2","key":"22_CR9","doi-asserted-by":"publisher","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. Comput. Complexity\u00a07(2), 163\u2013173 (1998)","journal-title":"Comput. Complexity"},{"key":"22_CR10","unstructured":"Deutsch, D., Jozsa, R.: Rapid solution of problems by quantum computation. Proc. of the Royal Society A\u00a0439 (1985)"},{"key":"22_CR11","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 Sm with the octahedral triangulation. J. Combinatorial Theory\u00a02, 588\u2013602 (1967)","journal-title":"J. Combinatorial Theory"},{"key":"22_CR12","unstructured":"Friedl, K., Ivanyos, G., Santha, M., Verhoeven, Y.: On the black-box complexity of Sperner\u2019s Lemma, \n                    \n                      http:\/\/xxx.lanl.gov\/abs\/quant-ph\/0505185"},{"key":"22_CR13","doi-asserted-by":"publisher","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\u00a05(3), 391\u2013407 (1984)","journal-title":"J. Algorithms"},{"key":"22_CR14","doi-asserted-by":"crossref","unstructured":"Laplante, S., Magniez, F.: Lower bounds for randomized and quantum query complexity using kolmogorov arguments. In: 19th Conference on Computational Complexity, pp. 294\u2013304 (2004)","DOI":"10.1109\/CCC.2004.1313852"},{"issue":"2","key":"22_CR15","doi-asserted-by":"publisher","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.\u00a043(2), 131\u2013153 (1993)","journal-title":"Discrete Appl. Math."},{"issue":"2","key":"22_CR16","doi-asserted-by":"publisher","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.\u00a023(2), 157\u2013178 (1989)","journal-title":"Discrete Appl. Math."},{"key":"22_CR17","doi-asserted-by":"publisher","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. Theoret. Comput. Sci.\u00a081, 317\u2013324 (1991)","journal-title":"Theoret. Comput. Sci."},{"key":"22_CR18","doi-asserted-by":"crossref","unstructured":"Papadimitriou, C.: On graph-theoretic lemmata and complexity classes. In: 31st FOCS, pp. 794\u2013801 (1990)","DOI":"10.1109\/FSCS.1990.89602"},{"issue":"3","key":"22_CR19","doi-asserted-by":"publisher","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.\u00a048(3), 498\u2013532 (1994)","journal-title":"J. Comput. System Sci."},{"key":"22_CR20","doi-asserted-by":"crossref","unstructured":"Santha, M., Szegedy, M.: Quantum and classical query complexities of local search are polynomially related. In: 36th STOC, pp. 494\u2013501 (2004)","DOI":"10.1145\/1007352.1007427"},{"key":"22_CR21","unstructured":"Shi, Y.: Quantum lower bounds for the collision and the element distinctness problems. In: 43rd FOCS, pp. 513\u2013519 (2002)"},{"issue":"26","key":"22_CR22","doi-asserted-by":"publisher","first-page":"1474","DOI":"10.1137\/S0097539796298637","volume":"5","author":"D. Simon","year":"1997","unstructured":"Simon, D.: On the power of quantum computation. SIAM J. on Computing\u00a05(26), 1474\u20131783 (1997)","journal-title":"SIAM J. on Computing"},{"key":"22_CR23","doi-asserted-by":"publisher","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. Sem. Hamburg Univ.\u00a06, 265\u2013272 (1928)","journal-title":"Abh. Math. Sem. Hamburg Univ."},{"key":"22_CR24","unstructured":"\u0160palek, R., Szegedy, M.: All quantum adversary methods are equivalent, \n                    \n                      http:\/\/xxx.lanl.gov\/abs\/quant-ph\/0409116"},{"key":"22_CR25","unstructured":"Taylor, L.: Sperner\u2019s Lemma, Brouwer\u2019s Fixed Point Theorem, The Fundamental Theorem of Algebra, \n                    \n                      http:\/\/www.cs.csubak.edu\/~larry\/math\/sperner.pdf"},{"key":"22_CR26","doi-asserted-by":"publisher","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.\u00a03, 259\u2013268 (1978)","journal-title":"Ann. Discrete Math."}],"container-title":["Lecture Notes in Computer Science","Fundamentals of Computation Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11537311_22.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T02:52:42Z","timestamp":1619491962000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11537311_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540281931","9783540318736"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/11537311_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}