{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,22]],"date-time":"2025-03-22T04:18:19Z","timestamp":1742617099070,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540164869"},{"type":"electronic","value":"9783540398257"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1986]]},"DOI":"10.1007\/3-540-16486-3_96","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T18:45:26Z","timestamp":1330195526000},"page":"163-183","source":"Crossref","is-referenced-by-count":1,"title":["Two lower bound arguments with \"inaccessible\" numbers"],"prefix":"10.1007","author":[{"given":"Martin","family":"Dietzfelbinger","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wolfgang","family":"Maass","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,2]]},"reference":[{"key":"12_CR1","unstructured":"A.V. Aho, J.E. Hopcroft, J.D. Ullman, The Design and Analysis of Computer Algorithms, Reading, Mass., 1974."},{"key":"12_CR2","doi-asserted-by":"crossref","unstructured":"M. Ben-Or, Lower bounds for algebraic computation trees, Proc. 15th STOC (1983), 80\u201386.","DOI":"10.1145\/800061.808735"},{"key":"12_CR3","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1016\/0022-0000(78)90026-0","volume":"16","author":"D.P. Dobkin","year":"1978","unstructured":"D.P. Dobkin and R.J. Lipton, A lower bound of n2\/2 on linear search programs for the knapsack problem, J. Comput. System Sci. 16(1978), 413\u2013417.","journal-title":"J. Comput. System Sci."},{"key":"12_CR4","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/0022-0000(79)90054-0","volume":"18","author":"D.P. Dobkin","year":"1979","unstructured":"D.P. Dobkin and R.J. Lipton, On the complexity of computations under varying sets of primitives, J. Comput. System Sci. 18(1979), 86\u201391.","journal-title":"J. Comput. System Sci."},{"key":"12_CR5","volume-title":"Ramsey Theory","author":"R.L. Graham","year":"1980","unstructured":"R.L. Graham, B.L. Rothschild, J.H. Spencer, Ramsey Theory (Wiley, New York 1980)."},{"key":"12_CR6","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1007\/BF00290735","volume":"19","author":"P. Klein","year":"1983","unstructured":"P. Klein and F. Meyer auf der Heide, A lower time bound for the knapsack problem on random access machines, Acta Informatica 19(1983), 385\u2013395.","journal-title":"Acta Informatica"},{"key":"12_CR7","unstructured":"W. Maass, An optimal quadratic lower bound for random access machines and other applications of Ramsey's theorem, Preliminary Report (Berkeley, 1984)."},{"key":"12_CR8","unstructured":"W. Maass, On the use of inaccessible numbers and order indiscernibles in lower bound arguments for random access machines, U. of Ill. at Chicago, Res. Report in C. Sc. No.4 (to appear in the Journal of Symbolic Logic)"},{"key":"12_CR9","doi-asserted-by":"crossref","unstructured":"S. Moran, M. Snir and U. Manber, Applications of Ramsey's theorem to decision tree complexity, Proc. of 25th FOCS 1984, 332\u2013337.","DOI":"10.1109\/SFCS.1984.715933"},{"key":"12_CR10","doi-asserted-by":"crossref","first-page":"938","DOI":"10.1145\/4221.4259","volume":"32","author":"S. Moran","year":"1985","unstructured":"S. Moran, M. Snir and U. Manber, Applications of Ramsey's theorem to decision tree complexity, J. of the ACM 32(1985), 938\u2013949.","journal-title":"J. of the ACM"},{"key":"12_CR11","doi-asserted-by":"crossref","unstructured":"F. Meyer auf der Heide, A polynomial linear search algorithm for the n-dimensional knapsack problem, Proc. 15th Ann. ACM Symp. on Theory of Computing (1983), 70\u201379.","DOI":"10.1145\/800061.808734"},{"key":"12_CR12","unstructured":"F. Meyer auf der Heide, Lower bounds for solving linear diophantine equations on random access machines, Tech. Report 6\/84 (Universitaet Frankfurt)."},{"key":"12_CR13","doi-asserted-by":"crossref","unstructured":"F. Meyer auf der Heide, Fast algorithms for n-dimensional restrictions of hard problems, Proc. 17th ACM STOC (1985), 413\u2013420.","DOI":"10.1145\/22145.22191"},{"key":"12_CR14","unstructured":"W.J. Paul and J. Simon, Decision trees and random access machines, Proc. Symp. Logik und Algorithmik (Zuerich, 1980), 331\u2013339."},{"key":"12_CR15","unstructured":"G.E. Sacks, Saturated model theory (Benjamin, Reading 1972)."},{"key":"12_CR16","first-page":"181","volume":"23","author":"E. Ukkonen","year":"1983","unstructured":"E. Ukkonen, Exponential lower bounds for some NP-complete problems in a restricted linear decision tree model, B.I.T. 23 (1983), 181\u2013192.","journal-title":"B.I.T."}],"container-title":["Lecture Notes in Computer Science","Structure in Complexity Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-16486-3_96.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T20:27:48Z","timestamp":1742588868000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-16486-3_96"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1986]]},"ISBN":["9783540164869","9783540398257"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/3-540-16486-3_96","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1986]]}}}