{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,30]],"date-time":"2026-01-30T04:59:43Z","timestamp":1769749183891,"version":"3.49.0"},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2023,3,21]],"date-time":"2023-03-21T00:00:00Z","timestamp":1679356800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100006769","name":"Russian Science Foundation","doi-asserted-by":"crossref","award":["20-11-20203"],"award-info":[{"award-number":["20-11-20203"]}],"id":[{"id":"10.13039\/501100006769","id-type":"DOI","asserted-by":"crossref"}]},{"name":"National Science Foundation","award":["CCF 1811729"],"award-info":[{"award-number":["CCF 1811729"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2023,4,30]]},"abstract":"<jats:p>\n            In a lossless compression system with target lengths, a compressor \ud835\udc9e maps an integer\n            <jats:italic>m<\/jats:italic>\n            and a binary string\n            <jats:italic>x<\/jats:italic>\n            to an\n            <jats:italic>m<\/jats:italic>\n            -bit code\n            <jats:italic>p<\/jats:italic>\n            , and if\n            <jats:italic>m<\/jats:italic>\n            is sufficiently large, a decompressor \ud835\udc9f reconstructs\n            <jats:italic>x<\/jats:italic>\n            from\n            <jats:italic>p<\/jats:italic>\n            . We call a pair (\n            <jats:italic>m,x<\/jats:italic>\n            )\n            <jats:italic>achievable<\/jats:italic>\n            for (\ud835\udc9e,\ud835\udc9f) if this reconstruction is successful. We introduce the notion of an optimal compressor \ud835\udc9e\n            <jats:sub>opt<\/jats:sub>\n            by the following universality property: For any compressor-decompressor pair (\ud835\udc9e,\ud835\udc9f), there exists a decompressor \ud835\udc9f\n            <jats:sup>\u2032<\/jats:sup>\n            such that if\n            <jats:italic>(m,x)<\/jats:italic>\n            is achievable for (\ud835\udc9e,\ud835\udc9f), then (\n            <jats:italic>m<\/jats:italic>\n            + \u0394 ,\n            <jats:italic>x<\/jats:italic>\n            ) is achievable for (\ud835\udc9e\n            <jats:sub>opt<\/jats:sub>\n            , \ud835\udc9f\n            <jats:sup>\u2032<\/jats:sup>\n            ), where \u0394 is some small value called the overhead. We show that there exists an optimal compressor that has only polylogarithmic overhead and works in probabilistic polynomial time. Differently said, for any pair (\ud835\udc9e,\ud835\udc9f), no matter how slow \ud835\udc9e is, or even if \ud835\udc9e is non-computable, \ud835\udc9e\n            <jats:sub>\n              <jats:italic>opt<\/jats:italic>\n            <\/jats:sub>\n            is a fixed compressor that in polynomial time produces codes almost as short as those of \ud835\udc9e. The cost is that the corresponding decompressor is slower.\n          <\/jats:p>\n          <jats:p>We also show that each such optimal compressor can be used for distributed compression, in which case it can achieve optimal compression rates as given in the Slepian\u2013Wolf theorem and even for the Kolmogorov complexity variant of this theorem.<\/jats:p>","DOI":"10.1145\/3575807","type":"journal-article","created":{"date-parts":[[2022,12,14]],"date-time":"2022-12-14T12:16:24Z","timestamp":1671020184000},"page":"1-33","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Universal almost Optimal Compression and Slepian-wolf Coding in Probabilistic Polynomial Time"],"prefix":"10.1145","volume":"70","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6138-0591","authenticated-orcid":false,"given":"Bruno","family":"Bauwens*","sequence":"first","affiliation":[{"name":"National Research University Higher School of Economics, Moscow, Russia"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5938-6599","authenticated-orcid":false,"given":"Marius","family":"Zimand","sequence":"additional","affiliation":[{"name":"Towson University, Towson, MD, USA"}]}],"member":"320","published-online":{"date-parts":[[2023,3,21]]},"reference":[{"key":"e_1_3_4_2_1","doi-asserted-by":"crossref","unstructured":"B. Bauwens A. Makhlin N. Vereshchagin and M. Zimand. 2018. Short lists with short programs in short time. Comput. Complex. 27 1 (2018) 31\u201361.","DOI":"10.1007\/s00037-017-0154-2"},{"key":"e_1_3_4_3_1","first-page":"241","volume-title":"Proceedings of the IEEE 29th Conference on Computational Complexity","author":"Bauwens Bruno","year":"2014","unstructured":"Bruno Bauwens and Marius Zimand. 2014. Linear list-approximation for short programs (or the power of a few random bits). In Proceedings of the IEEE 29th Conference on Computational Complexity. IEEE, 241\u2013247. DOI:DOI:10.1109\/CCC.2014.32"},{"key":"e_1_3_4_4_1","first-page":"124","article-title":"Entropy and the complexity of the trajectories of a dynamic system","volume":"44","author":"Brudno A. A.","year":"1982","unstructured":"A. A. Brudno. 1982. Entropy and the complexity of the trajectories of a dynamic system. Trudy Moskovskogo Matematicheskogo Obshchestva 44 (1982), 124\u2013149.","journal-title":"Trudy Moskovskogo Matematicheskogo Obshchestva"},{"key":"e_1_3_4_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2007.03.015"},{"key":"e_1_3_4_6_1","doi-asserted-by":"crossref","first-page":"659","DOI":"10.1145\/509907.510003","volume-title":"Proceedings of the STOC.","author":"Capalbo M. R.","year":"2002","unstructured":"M. R. Capalbo, O. Reingold, S. P. Vadhan, and A. Wigderson. 2002. Randomness conductors and constant-degree lossless expanders. In Proceedings of the STOC.John H. Reif (Ed.), ACM, 659\u2013668."},{"key":"e_1_3_4_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1975.1055356"},{"key":"e_1_3_4_8_1","volume-title":"Elements of Information Theory","author":"Cover Thomas M.","year":"2006","unstructured":"Thomas M. Cover and Joy A. Thomas. 2006. Elements of Information Theory (2nd ed.). Wiley."},{"key":"e_1_3_4_9_1","first-page":"437","article-title":"The Slepian-Wolf theorem for individual sequences","volume":"14","author":"Dueck G.","year":"1985","unstructured":"G. Dueck and L. Wolters. 1985. The Slepian-Wolf theorem for individual sequences. Problems of Control and Information Theory 14, 6 (1985), 437\u2013450.","journal-title":"Problems of Control and Information Theory"},{"issue":"4","key":"e_1_3_4_10_1","article-title":"Unbalanced expanders and randomness extractors from Parvaresh\u2013Vardy codes","volume":"56","author":"Guruswami Venkatesan","year":"2009","unstructured":"Venkatesan Guruswami, Christopher Umans, and Salil P. Vadhan. 2009. Unbalanced expanders and randomness extractors from Parvaresh\u2013Vardy codes. Journal of the ACM 56, 4 (2009), 1\u201334.","journal-title":"Journal of the ACM"},{"key":"e_1_3_4_11_1","volume-title":"Information-spectrum Methods in Information Theory","author":"Han Te Sun","year":"2003","unstructured":"Te Sun Han. 2003. Information-spectrum Methods in Information Theory. Springer Verlag."},{"key":"e_1_3_4_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.256486"},{"key":"e_1_3_4_13_1","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1080\/01621459.1963.10500830","article-title":"Probability inequalities for sums of bounded random variables","volume":"58","author":"Hoeffding Wassily","year":"1963","unstructured":"Wassily Hoeffding. 1963. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Society 58, 301 (1963), 13\u201330.","journal-title":"Journal of the American Statistical Society"},{"issue":"7","key":"e_1_3_4_14_1","doi-asserted-by":"crossref","first-page":"1129","DOI":"10.1016\/S0893-9659(03)90105-4","article-title":"A note on Kolmogorov complexity and entropy","volume":"16","author":"Horibe Yasuichi","year":"2003","unstructured":"Yasuichi Horibe. 2003. A note on Kolmogorov complexity and entropy. Applied Mathematics Letters 16, 7 (2003), 1129\u20131130.","journal-title":"Applied Mathematics Letters"},{"issue":"9","key":"e_1_3_4_15_1","doi-asserted-by":"crossref","first-page":"1098","DOI":"10.1109\/JRPROC.1952.273898","article-title":"A method for the construction of minimum-redundancy codes","volume":"40","author":"Huffman D.A.","year":"1952","unstructured":"D.A. Huffman. 1952. A method for the construction of minimum-redundancy codes. Proceedings of the IRE 40, 9 (1952), 1098\u20131101.","journal-title":"Proceedings of the IRE"},{"key":"e_1_3_4_16_1","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-17364-6","volume-title":"Extremal Combinatorics","author":"Jukna S.","year":"2011","unstructured":"S. Jukna. 2011. Extremal Combinatorics. Springer Verlag. 2nd edition."},{"issue":"10","key":"e_1_3_4_17_1","doi-asserted-by":"crossref","first-page":"2393","DOI":"10.1587\/transfun.E92.A.2393","article-title":"Slepian-Wolf coding of individual sequences based on ensembles of linear functions","volume":"92","author":"Kuzuoka S.","year":"2009","unstructured":"S. Kuzuoka. 2009. Slepian-Wolf coding of individual sequences based on ensembles of linear functions. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E92-A, 10 (2009), 2393\u20132401.","journal-title":"IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences"},{"key":"e_1_3_4_18_1","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1109\/TIT.1976.1055501","article-title":"On the complexity of finite sequences","volume":"22","author":"Lempel A.","year":"1976","unstructured":"A. Lempel and J. Ziv. 1976. On the complexity of finite sequences. IEEE Transactions on Information Theory IT-22 2, 1 (1976), 75\u201381.","journal-title":"IEEE Transactions on Information Theory"},{"key":"e_1_3_4_19_1","volume-title":"An Introduction to Kolmogorov Complexity and Its Applications","author":"Li Ming","year":"2019","unstructured":"Ming Li and Paul M. B. Vit\u00e1nyi. 2019. An Introduction to Kolmogorov Complexity and Its Applications. Springer. Fourth edition (First edition 1993)."},{"key":"e_1_3_4_20_1","first-page":"1063","article-title":"Coding theorems on correlated general sources","volume":"78","author":"Miyake S.","year":"1995","unstructured":"S. Miyake and F. Kanaya. 1995. Coding theorems on correlated general sources. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Science E78-A(9) (1995), 1063\u20131070.","journal-title":"IEICE Transactions on Fundamentals of Electronics, Communications and Computer Science"},{"issue":"1","key":"e_1_3_4_21_1","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1016\/S0304-3975(01)00033-0","article-title":"Conditional complexity and codes","volume":"271","author":"Muchnik Andrei A.","year":"2002","unstructured":"Andrei A. Muchnik. 2002. Conditional complexity and codes. Theoretical Computer Science 271, 1\u20132 (2002), 97\u2013109.","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"e_1_3_4_22_1","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1007\/s00224-011-9321-z","article-title":"Variations on Muchnik\u2019s conditional complexity theorem","volume":"49","author":"Musatov D.","year":"2011","unstructured":"D. Musatov, A. E. Romashchenko, and A. Shen. 2011. Variations on Muchnik\u2019s conditional complexity theorem. Theory of Computing Systems 49, 2 (2011), 227\u2013245.","journal-title":"Theory of Computing Systems"},{"key":"e_1_3_4_23_1","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1006\/jcss.1996.0004","article-title":"Randomness is linear in space","volume":"52","author":"Nisan N.","year":"1996","unstructured":"N. Nisan and D. Zuckerman. 1996. Randomness is linear in space. Journal of Computer and System Sciences 52, 1 (1996), 43\u201352.","journal-title":"Journal of Computer and System Sciences"},{"issue":"1","key":"e_1_3_4_24_1","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1137\/S0895480197329508","article-title":"Tight bounds for dispersers, extractors, and depth-two superconcentrators","volume":"13","author":"Radhakrishnan J.","year":"2000","unstructured":"J. Radhakrishnan and A. Ta-Shma. 2000. Tight bounds for dispersers, extractors, and depth-two superconcentrators. SIAM Journal on Discrete Mathematics 13, 1(2000), 2\u201324.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"e_1_3_4_25_1","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1145\/301250.301294","volume-title":"Proceedings of the STOC.","author":"Raz Ran","year":"1999","unstructured":"Ran Raz and Omer Reingold. 1999. On recycling the randomness of states in space bounded computation. In Proceedings of the STOC.Jeffrey Scott Vitter, Lawrence L. Larmore, and Frank Thomson Leighton (Eds.), ACM, 159\u2013168."},{"key":"e_1_3_4_26_1","first-page":"149","volume-title":"Proceedings of the 30th ACM Symposium on Theory of Computing","author":"Raz R.","year":"1999","unstructured":"R. Raz, O. Reingold, and S. Vadhan. 1999. Extracting all the randomness and reducing the error in Trevisan\u2019s extractor. In Proceedings of the 30th ACM Symposium on Theory of Computing. ACM, 149\u2013158."},{"key":"e_1_3_4_27_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2002.1824"},{"issue":"1","key":"e_1_3_4_28_1","first-page":"20","article-title":"Complexity interpretation for the fork network coding","volume":"5","author":"Romashchenko A.","year":"2005","unstructured":"A. Romashchenko. 2005. Complexity interpretation for the fork network coding. Information Processes 5, 1 (2005), 20\u201328. In Russian. Available in English as [Romashchenko 2016].","journal-title":"Information Processes"},{"key":"e_1_3_4_29_1","unstructured":"Andrei Romashchenko. 2016. Coding in the fork network in the framework of Kolmogorov complexity. arXiv:1602.02648. Retrieved from http:\/\/arxiv.org\/abs\/1602.02648."},{"key":"e_1_3_4_30_1","doi-asserted-by":"crossref","DOI":"10.1002\/j.1538-7305.1948.tb01338.x","article-title":"A mathematical theory of communication","volume":"27","author":"Shannon C. E.","year":"1948","unstructured":"C. E. Shannon. 1948. A mathematical theory of communication. The Bell System Technical Journal 27, 3 (1948), 379\u2013423.","journal-title":"The Bell System Technical Journal"},{"key":"e_1_3_4_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1973.1055037"},{"issue":"2","key":"e_1_3_4_32_1","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1007\/s00493-007-0053-2","article-title":"Lossless condensers, unbalanced expanders, and extractors","volume":"27","author":"Ta-Shma A.","year":"2007","unstructured":"A. Ta-Shma, C. Umans, and D. Zuckerman. 2007. Lossless condensers, unbalanced expanders, and extractors. Combinatorica 27, 2 (2007), 213\u2013240.","journal-title":"Combinatorica"},{"key":"e_1_3_4_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-014-0090-3"},{"key":"e_1_3_4_34_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000010"},{"issue":"6","key":"e_1_3_4_35_1","doi-asserted-by":"crossref","first-page":"872","DOI":"10.1109\/5.286191","article-title":"The sliding window Lempel-Ziv is asymptotically optimal","volume":"2","author":"Wyner A. D.","year":"1994","unstructured":"A. D. Wyner and J. Ziv. 1994. The sliding window Lempel-Ziv is asymptotically optimal. Proc. IEEE 2, 6 (1994), 872\u2013877.","journal-title":"Proc. IEEE"},{"key":"e_1_3_4_36_1","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1007\/978-3-319-08019-2_42","volume-title":"Proceedings of the Language, Life, Limits - 10th Conference on Computability in Europe.","volume":"8493","author":"Zimand Marius","year":"2014","unstructured":"Marius Zimand. 2014. Short lists with short programs in short time - A short proof. In Proceedings of the Language, Life, Limits - 10th Conference on Computability in Europe.Arnold Beckmann, Erzs\u00e9bet Csuhaj-Varj\u00fa, and Klaus Meer (Eds.), Lecture Notes in Computer Science, Vol. 8493, Springer, 403\u2013408. DOI:DOI:10.1007\/978-3-319-08019-2_42"},{"key":"e_1_3_4_37_1","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1145\/3055399.3055421","volume-title":"Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing.","author":"Zimand Marius","year":"2017","unstructured":"Marius Zimand. 2017. Kolmogorov complexity version of Slepian-Wolf coding. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing.Hamed Hatami, Pierre McKenzie, and Valerie King (Eds.), ACM, 22\u201332. DOI:DOI:10.1145\/3055399.3055421"},{"key":"e_1_3_4_38_1","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1109\/TIT.1978.1055911","article-title":"Coding theorems for individual sequences","volume":"24","author":"Ziv J.","year":"1978","unstructured":"J. Ziv. 1978. Coding theorems for individual sequences. IEEE Transactions on Information Theory IT-24, 4 (1978), 405\u2013412.","journal-title":"IEEE Transactions on Information Theory"},{"key":"e_1_3_4_39_1","first-page":"348\u2013352\u2013412","article-title":"Fixed-rate encoding of individual sequences with side information","volume":"30","author":"Ziv J.","year":"1984","unstructured":"J. Ziv. 1984. Fixed-rate encoding of individual sequences with side information. IEEE Transactions on Information Theory IT-30, 2 (1984), 348\u2013352\u2013412.","journal-title":"IEEE Transactions on Information Theory"},{"issue":"6","key":"e_1_3_4_40_1","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1070\/RM1970v025n06ABEH001269","article-title":"The complexity of finite objects and the development of the concepts of information and randomness by means of the theory of algorithms","volume":"25","author":"Zvonkin A.","year":"1970","unstructured":"A. Zvonkin and L. Levin. 1970. The complexity of finite objects and the development of the concepts of information and randomness by means of the theory of algorithms. Russian Mathematical Surveys 25, 6 (1970), 83\u2013124.","journal-title":"Russian Mathematical Surveys"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3575807","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3575807","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:51:21Z","timestamp":1750182681000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3575807"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,3,21]]},"references-count":39,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,4,30]]}},"alternative-id":["10.1145\/3575807"],"URL":"https:\/\/doi.org\/10.1145\/3575807","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,3,21]]},"assertion":[{"value":"2019-11-27","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-11-19","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-03-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}