{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T16:40:33Z","timestamp":1787503233934,"version":"build-2736575974"},"publisher-location":"Berlin, Heidelberg","reference-count":10,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540323013","type":"print"},{"value":"9783540322887","type":"electronic"}],"license":[{"start":{"date-parts":[[2006,1,1]],"date-time":"2006-01-01T00:00:00Z","timestamp":1136073600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11672142_10","type":"book-chapter","created":{"date-parts":[[2006,2,28]],"date-time":"2006-02-28T03:27:54Z","timestamp":1141097274000},"page":"137-148","source":"Crossref","is-referenced-by-count":10,"title":["Kolmogorov Complexity with Error"],"prefix":"10.1007","author":[{"given":"Lance","family":"Fortnow","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Troy","family":"Lee","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nikolai","family":"Vereshchagin","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"10_CR1","volume-title":"Covering Codes","author":"G. Cohen","year":"1997","unstructured":"Cohen, G., Honkala, I., Litsyn, S., Lobstein, A.: Covering Codes. North-Holland, Amsterdam (1997)"},{"key":"10_CR2","volume-title":"Introduction to Algorithms","author":"T. Cormen","year":"1990","unstructured":"Cormen, T., Leiserson, C., Rivest, R.: Introduction to Algorithms. MIT Press, Cambridge (1990)"},{"key":"10_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1007\/3-540-45022-X_21","volume-title":"Proceedings of the 27th International Colloquium On Automata, Languages and Programming","author":"E. Dantsin","year":"2000","unstructured":"Dantsin, E., Goerdt, A., Hirsch, E., Sch\u00f6ning, U.: Deterministic algorithms for k-SAT based on covering codes and local search. In: Proceedings of the 27th International Colloquium On Automata, Languages and Programming. LNCS, pp. 236\u2013247. Springer, Heidelberg (2000)"},{"key":"10_CR4","first-page":"1","volume-title":"Proceedings of the 32nd ACM Symposium on the Theory of Computing","author":"R. Impagliazzo","year":"2000","unstructured":"Impagliazzo, R., Shaltiel, R., Wigderson, A.: Extractors and pseudo-random generators with optimal seed length. In: Proceedings of the 32nd ACM Symposium on the Theory of Computing, pp. 1\u201310. ACM, New York (2000)"},{"key":"10_CR5","doi-asserted-by":"publisher","first-page":"1812","DOI":"10.1109\/TIT.2003.813490","volume":"49","author":"M. Krivelevich","year":"2003","unstructured":"Krivelevich, M., Sudakov, B., Vu, V.: Covering codes with improved density. IEEE Transactions on Information Theory\u00a049, 1812\u20131815 (2003)","journal-title":"IEEE Transactions on Information Theory"},{"key":"10_CR6","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-2606-0","volume-title":"An Introduction to Kolmogorov Complexity and its Applications","author":"M. Li","year":"1997","unstructured":"Li, M., Vit\u00e1nyi, P.: An Introduction to Kolmogorov Complexity and its Applications, 2nd edn. Springer, New York (1997)","edition":"2"},{"key":"10_CR7","volume-title":"Randomized Algorithms","author":"R. Motwani","year":"1997","unstructured":"Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, Cambridge (1997)"},{"issue":"11","key":"10_CR8","doi-asserted-by":"publisher","first-page":"2595","DOI":"10.1109\/78.482110","volume":"43","author":"B. Natarajan","year":"1995","unstructured":"Natarajan, B.: Filtering random noise from deterministic signals via data compression. IEEE transactions on signal processing\u00a043(11), 2595\u20132605 (1995)","journal-title":"IEEE transactions on signal processing"},{"key":"10_CR9","unstructured":"Vereschagin, N., Vit\u00e1nyi, P.: Algorithmic rate-distortion theory (2004), \n                  \n                    http:\/\/arxiv.org\/abs\/cs.IT\/0411014"},{"key":"10_CR10","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1070\/RM1970v025n06ABEH001269","volume":"25","author":"A. Zvonkin","year":"1970","unstructured":"Zvonkin, A., Levin, L.: The complexity of finite objects and the algorithmic concepts of information and randomness. Russian Mathematical Surveys\u00a025, 83\u2013124 (1970)","journal-title":"Russian Mathematical Surveys"}],"container-title":["Lecture Notes in Computer Science","STACS 2006"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11672142_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,12]],"date-time":"2019-03-12T02:42:05Z","timestamp":1552358525000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11672142_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540323013","9783540322887"],"references-count":10,"URL":"https:\/\/doi.org\/10.1007\/11672142_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006]]}}}