{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,20]],"date-time":"2025-02-20T05:19:22Z","timestamp":1740028762145,"version":"3.37.3"},"publisher-location":"Berlin, Heidelberg","reference-count":10,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540006237"},{"type":"electronic","value":"9783540364948"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/3-540-36494-3_19","type":"book-chapter","created":{"date-parts":[[2010,3,29]],"date-time":"2010-03-29T21:12:04Z","timestamp":1269897124000},"page":"203-211","source":"Crossref","is-referenced-by-count":3,"title":["On the Complexity of Finding a Local Maximum of Functions on Discrete Planar Subsets"],"prefix":"10.1007","author":[{"given":"Anton","family":"Mityagin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2003,2,17]]},"reference":[{"key":"19_CR1","doi-asserted-by":"crossref","unstructured":"R. Impagliazzo, M. Naor. Decision Trees and Downward Closures, Third Annual Conference on Structure in Complexity Theory, pp. 29\u201338, 1988.","DOI":"10.1109\/SCT.1988.5260"},{"key":"19_CR2","doi-asserted-by":"publisher","first-page":"860","DOI":"10.1137\/0132073","volume":"32","author":"D. Wang","year":"1977","unstructured":"D. Wang, P. Wang. Discrete isoperimetric problems. SIAM J. Appl.Math. vol. 32, pp 860\u2013870, 1977.","journal-title":"SIAM J. Appl.Math."},{"key":"19_CR3","doi-asserted-by":"crossref","unstructured":"M. Blum and R. Impagliazzo. General oracle and oracle classes. 28th Annual IEEE Symposium on Foundation of Computer Science, pp 118\u2013126, 1987.","DOI":"10.1109\/SFCS.1987.30"},{"key":"19_CR4","unstructured":"L. Beklemishev. On the induction schema for decidable predicates. Department of Philosophy, Utrecht University, Logic Group Preprint series, 2000."},{"key":"19_CR5","doi-asserted-by":"crossref","unstructured":"M. Santha. On the Monte Carlo boolean decision tree complexity of read-once formulae. In 6th Annual Conference on Structure in Complexity Theory, pp 180\u2013187, 1991.","DOI":"10.1109\/SCT.1991.160259"},{"key":"19_CR6","unstructured":"A. Rastsvetaev and L. Beklemishev. On the query complexity of finding a local maximum point. Department of Philosophy, Utrecht University, Logic Group Preprint Series 206, 2000. To appear in Information Processing Letters."},{"key":"19_CR7","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1007\/BF02125350","volume":"9","author":"G. Tardos","year":"1990","unstructured":"G. Tardos. Query complexity or why is it difficult to separate NPA \u2229 Co-NPA from PA by a random oracle. Combinatorica, 9:385\u2013392, 1990. On the Complexity of Finding a Local Maximum of Functions 211","journal-title":"Combinatorica"},{"key":"19_CR8","doi-asserted-by":"crossref","unstructured":"L. Lovasz, M. Naor, I. Newman, A. Wigderson. Search problems in the decision tree model. 32th FOCS, pp 576\u2013585, 1991.","DOI":"10.1109\/SFCS.1991.185422"},{"key":"19_CR9","doi-asserted-by":"crossref","first-page":"502","DOI":"10.1090\/S0002-9939-1953-0055639-3","volume":"4","author":"J. Kiefer","year":"1953","unstructured":"J. Kiefer. Sequential minimax search for a maximum. Proc. Amer. Math. Soc., 4, pp 502\u2013506, 1953.","journal-title":"Proc. Amer. Math. Soc."},{"key":"19_CR10","doi-asserted-by":"crossref","unstructured":"P. Crescenzi, R. Silvestri. Sperner\u2019s lemma and Robust Machines. Eighth annual structure in complexity theory conference, pp 194\u2013199, 1993.","DOI":"10.1109\/SCT.1993.336527"}],"container-title":["Lecture Notes in Computer Science","STACS 2003"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-36494-3_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,19]],"date-time":"2025-02-19T19:14:23Z","timestamp":1739992463000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-36494-3_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540006237","9783540364948"],"references-count":10,"URL":"https:\/\/doi.org\/10.1007\/3-540-36494-3_19","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2003]]}}}