{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,5]],"date-time":"2026-10-05T08:58:10Z","timestamp":1791190690430,"version":"4.1.0"},"publisher-location":"Berlin, Heidelberg","reference-count":11,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540359043","type":"print"},{"value":"9783540359050","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11786986_43","type":"book-chapter","created":{"date-parts":[[2006,6,28]],"date-time":"2006-06-28T06:46:45Z","timestamp":1151477205000},"page":"489-500","source":"Crossref","is-referenced-by-count":17,"title":["On the Complexity of 2D Discrete Fixed Point Problem"],"prefix":"10.1007","author":[{"given":"Xi","family":"Chen","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xiaotie","family":"Deng","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"43_CR1","doi-asserted-by":"crossref","unstructured":"Chen, X., Deng, X.: On Algorithms for Discrete and Approximate Brouwer Fixed Points. In: STOC 2005, pp. 323\u2013330 (2005)","DOI":"10.1145\/1060590.1060638"},{"key":"43_CR2","doi-asserted-by":"crossref","unstructured":"Chen, X., Deng, X.: On the Complexity of 2D Discrete Fixed Point Problem. ECCC, TR06-037 (2006)","DOI":"10.1007\/11786986_43"},{"key":"43_CR3","doi-asserted-by":"crossref","unstructured":"Chen, X., Deng, X., Teng, S.-H.: Computing Nash equilibria: approximation and smoothed complexity. ECCC, TR06-023 (2006)","DOI":"10.1109\/FOCS.2006.20"},{"key":"43_CR4","doi-asserted-by":"crossref","unstructured":"Daskalakis, C., Goldberg, P.W., Papadimitriou, C.H.: The Complexity of Computing a Nash Equilibrium. STOC 2006 (2006)","DOI":"10.1145\/1132516.1132527"},{"key":"43_CR5","unstructured":"Friedl, K., Ivanyos, G., Santha, M., Verhoeven, Y.: Locally 2-dimensional Sperner problems complete for the Polynomial Parity Argument classes (submitted)"},{"key":"43_CR6","unstructured":"Friedl, K., Ivanyos, G., Santha, M., Verhoeven, Y.: On the complexity of Sperner\u2019s Lemma. Research report NI05002-QIS at the Isaac Newton Institute for Mathematical studies"},{"issue":"5-6","key":"43_CR7","doi-asserted-by":"publisher","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. Inform. Process. Lett.\u00a077(5-6), 255\u2013259 (2001)","journal-title":"Inform. Process. Lett."},{"key":"43_CR8","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1016\/0885-064X(89)90017-4","volume":"5","author":"M.D. Hirsch","year":"1989","unstructured":"Hirsch, M.D., Papadimitriou, C., Vavasis, S.: Exponential lower bounds for finding Brouwer fixed points. J.Complexity\u00a05, 379\u2013416 (1989)","journal-title":"J.Complexity"},{"key":"43_CR9","doi-asserted-by":"crossref","unstructured":"Papadimitriou, C.H.: On graph-theoretic lemmata and complexity classes. In: In Proceedings 31st Annual Symposium on Foundations of Computer Science, pp. 794\u2013801 (1990)","DOI":"10.1109\/FSCS.1990.89602"},{"key":"43_CR10","doi-asserted-by":"crossref","unstructured":"Papadimitriou, C.H.: On the complexity of the parity argument and other inefficient proofs of existence. In: JCSS, pp. 498\u2013532 (1994)","DOI":"10.1016\/S0022-0000(05)80063-7"},{"key":"43_CR11","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/BF02940617","volume":"6","author":"E. Sperner","year":"1928","unstructured":"Sperner, E.: Neuer Beweis fur die Invarianz der Dimensionszahl und des Gebietes. Abhandlungen aus dem Mathematischen Seminar Universitat Hamburg\u00a06, 265\u2013272 (1928)","journal-title":"Abhandlungen aus dem Mathematischen Seminar Universitat Hamburg"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11786986_43.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T03:19:52Z","timestamp":1619493592000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11786986_43"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540359043","9783540359050"],"references-count":11,"URL":"https:\/\/doi.org\/10.1007\/11786986_43","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006]]}}}