{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:46:32Z","timestamp":1725489992553},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540735441"},{"type":"electronic","value":"9783540735458"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-73545-8_15","type":"book-chapter","created":{"date-parts":[[2007,8,17]],"date-time":"2007-08-17T13:44:11Z","timestamp":1187358251000},"page":"129-139","source":"Crossref","is-referenced-by-count":3,"title":["Dimension, Halfspaces, and the Density of Hard Sets"],"prefix":"10.1007","author":[{"given":"Ryan C.","family":"Harkins","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"John M.","family":"Hitchcock","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"1\u20132","key":"15_CR1","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1016\/0304-3975(95)00073-9","volume":"158","author":"M. Agrawal","year":"1996","unstructured":"Agrawal, M., Arvind, V.: Geometric sets of low information content. Theoretical Computer Science\u00a0158(1\u20132), 193\u2013219 (1996)","journal-title":"Theoretical Computer Science"},{"key":"15_CR2","first-page":"1","volume-title":"Complexity Theory: Current Research","author":"V. Arvind","year":"1993","unstructured":"Arvind, V., Han, Y., Hemachandra, L., K\u00f6bler, J., Lozano, A., Mundhenk, M., Ogiwara, A., Sch\u00f6ning, U., Silvestri, R., Thierauf, T.: Reductions to sets of low information content. In: Ambos-Spies, K., Homer, S., Sch\u00f6ning, U. (eds.) Complexity Theory: Current Research, pp. 1\u201345. Cambridge University Press, Cambridge (1993)"},{"key":"15_CR3","unstructured":"Athreya, K.B., Hitchcock, J.M., Lutz, J.H., Mayordomo, E.: Effective strong dimension in algorithmic information and computational complexity. SIAM Journal on Computing (to appear)"},{"issue":"5","key":"15_CR4","doi-asserted-by":"publisher","first-page":"1082","DOI":"10.1137\/S0097539792237188","volume":"24","author":"B. Fu","year":"1995","unstructured":"Fu, B.: With quasilinear queries EXP is not polynomial time Turing reducible to sparse sets. SIAM Journal on Computing\u00a024(5), 1082\u20131090 (1995)","journal-title":"SIAM Journal on Computing"},{"key":"15_CR5","unstructured":"Fu, B.: Personal communication (2006)"},{"issue":"6","key":"15_CR6","doi-asserted-by":"publisher","first-page":"1696","DOI":"10.1137\/050647517","volume":"36","author":"J.M. Hitchcock","year":"2007","unstructured":"Hitchcock, J.M.: Online learning and resource-bounded dimension: Winnow yields new lower bounds for hard sets. SIAM Journal on Computing\u00a036(6), 1696\u20131708 (2007)","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"15_CR7","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1145\/1086649.1086662","volume":"36","author":"J.M. Hitchcock","year":"2005","unstructured":"Hitchcock, J.M., Lutz, J.H., Mayordomo, E.: The fractal geometry of complexity classes. SIGACT News\u00a036(3), 24\u201338 (2005)","journal-title":"SIGACT News"},{"issue":"2","key":"15_CR8","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1007\/s002249910010","volume":"33","author":"W. Lindner","year":"2000","unstructured":"Lindner, W., Schuler, R., Watanabe, O.: Resource-bounded measure and learnability. Theory of Computing Systems\u00a033(2), 151\u2013170 (2000)","journal-title":"Theory of Computing Systems"},{"issue":"4","key":"15_CR9","first-page":"285","volume":"2","author":"N. Littlestone","year":"1987","unstructured":"Littlestone, N.: Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm. Machine Learning\u00a02(4), 285\u2013318 (1987)","journal-title":"Machine Learning"},{"issue":"2","key":"15_CR10","doi-asserted-by":"publisher","first-page":"220","DOI":"10.1016\/0022-0000(92)90020-J","volume":"44","author":"J.H. Lutz","year":"1992","unstructured":"Lutz, J.H.: Almost everywhere high nonuniform complexity. Journal of Computer and System Sciences\u00a044(2), 220\u2013258 (1992)","journal-title":"Journal of Computer and System Sciences"},{"key":"15_CR11","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1007\/978-1-4612-1872-2_10","volume-title":"Complexity Theory Retrospective II","author":"J.H. Lutz","year":"1997","unstructured":"Lutz, J.H.: The quantitative structure of exponential time. In: Hemaspaandra, L.A., Selman, A.L. (eds.) Complexity Theory Retrospective II, pp. 225\u2013254. Springer, Heidelberg (1997)"},{"issue":"5","key":"15_CR12","doi-asserted-by":"publisher","first-page":"1236","DOI":"10.1137\/S0097539701417723","volume":"32","author":"J.H. Lutz","year":"2003","unstructured":"Lutz, J.H.: Dimension in complexity classes. SIAM Journal on Computing\u00a032(5), 1236\u20131259 (2003)","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"15_CR13","doi-asserted-by":"publisher","first-page":"762","DOI":"10.1137\/S0097539792237498","volume":"23","author":"J.H. Lutz","year":"1994","unstructured":"Lutz, J.H., Mayordomo, E.: Measure, stochasticity, and the density of hard languages. SIAM Journal on Computing\u00a023(4), 762\u2013779 (1994)","journal-title":"SIAM Journal on Computing"},{"key":"15_CR14","unstructured":"Lutz, J.H., Mayordomo, E.: Twelve problems in resource-bounded measure. Bulletin of the European Association for Theoretical Computer Science 68, 64\u201380 (1999). Current Trends in Theoretical Computer Science: Entering the 21st Century, pp. 83\u2013101. World Scientific Publishing, Singapore (2001)"},{"issue":"4","key":"15_CR15","doi-asserted-by":"publisher","first-page":"1197","DOI":"10.1137\/S0097539797321547","volume":"30","author":"J.H. Lutz","year":"2000","unstructured":"Lutz, J.H., Zhao, Y.: The density of weakly complete problems under adaptive reductions. SIAM Journal on Computing\u00a030(4), 1197\u20131210 (2000)","journal-title":"SIAM Journal on Computing"},{"key":"15_CR16","series-title":"Constraints and Prospects","first-page":"381","volume-title":"Computational Learning Theory and Natural Learning Systems","author":"W. Maass","year":"1994","unstructured":"Maass, W., Tur\u00e1n, G.: How fast can a threshold gate learn? In: Hanson, S.J., Drastal, G.A., Rivest, R.L. (eds.) Computational Learning Theory and Natural Learning Systems. Constraints and Prospects, vol.\u00a0I, pp. 381\u2013414. MIT Press, Cambridge (1994)"},{"key":"15_CR17","doi-asserted-by":"publisher","first-page":"338","DOI":"10.1109\/SFCS.1989.63500","volume-title":"Proceedings of the 30th IEEE Symposium on Foundations of Computer Science","author":"P.M. Vaidya","year":"1989","unstructured":"Vaidya, P.M.: A new algorithm for minimizing convex functions over convex sets. In: Proceedings of the 30th IEEE Symposium on Foundations of Computer Science, pp. 338\u2013349. IEEE Computer Society Press, Los Alamitos (1989)"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-73545-8_15.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T10:17:45Z","timestamp":1619518665000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-73545-8_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540735441","9783540735458"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-73545-8_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}