{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,12,1]],"date-time":"2024-12-01T05:04:33Z","timestamp":1733029473418,"version":"3.30.0"},"reference-count":60,"publisher":"IEEE","license":[{"start":{"date-parts":[[2024,10,27]],"date-time":"2024-10-27T00:00:00Z","timestamp":1729987200000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-029"},{"start":{"date-parts":[[2024,10,27]],"date-time":"2024-10-27T00:00:00Z","timestamp":1729987200000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-037"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024,10,27]]},"DOI":"10.1109\/focs61266.2024.00030","type":"proceedings-article","created":{"date-parts":[[2024,11,29]],"date-time":"2024-11-29T18:48:52Z","timestamp":1732906132000},"page":"369-378","source":"Crossref","is-referenced-by-count":0,"title":["Optimal Coding for Randomized Kolmogorov Complexity and Its Applications"],"prefix":"10.1109","author":[{"given":"Shuichi","family":"Hirahara","sequence":"first","affiliation":[{"name":"National Institute of Informatics,Tokyo,Japan"}]},{"given":"Zhenjian","family":"Lu","sequence":"additional","affiliation":[{"name":"University of Warwick,Coventry,UK"}]},{"given":"Mikito","family":"Nanashima","sequence":"additional","affiliation":[{"name":"Tokyo Institute of Technology,Tokyo,Japan"}]}],"member":"263","reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63486"},{"key":"ref2","first-page":"94:1","article-title":"An Efficient Coding Theorem via Probabilistic Representations and Its Applications","volume-title":"Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP)","author":"Lu","year":"2021"},{"volume-title":"Kolmogorov Complexity and Formula Size Lower Bounds","year":"2006","author":"Lee","key":"ref3"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1137\/0215020"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1561\/0400000004"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2009.12"},{"key":"ref7","first-page":"16: 1","article-title":"Probabilistic Kolmogorov Complexity with Applications to Average-Case Complexity","volume-title":"Proceedings of the Computational Complexity Conference (CCC)","author":"Goldberg","year":"2022"},{"key":"ref8","first-page":"92:1","article-title":"Optimal Coding Theorems in Time-Bounded Kolmogorov Complexity","volume-title":"Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP)","author":"Lu","year":"2022"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS57990.2023.00033"},{"key":"ref10","first-page":"32:1","article-title":"Randomness and Intractability in Kolmogorov Complexity","volume-title":"Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP)","author":"Oliveira","year":"2019"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1137\/0220034"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-005-0198-6"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2004.1313782"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-45198-3_18"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-72540-4_10"},{"key":"ref16","first-page":"66:1","article-title":"Incompressiblity and Next-Block Pseudoentropy","volume-title":"Proceedings of the Innovations in Theoretical Computer Science Conference (ITCS)","author":"Haitner","year":"2023"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00118"},{"key":"ref18","first-page":"35:1","article-title":"Hardness of KT Characterizes Parallel Cryptography","volume-title":"Proceedings of the Computational Complexity Conference (CCC)","author":"Ren","year":"2021"},{"key":"ref19","first-page":"11","article-title":"On the Possibility of Basing Cryptography on EXP\u2260 BPP","volume-title":"Proceedings of the International Cryptology Conference (CRYPTO)","author":"Liu","year":"2021"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3520051"},{"key":"ref21","first-page":"7:1","article-title":"One-Way Functions and a Conditional Variant of MKTP","volume-title":"Proceedings of the Foundations of Software Technology and Theoretical Computer Science (FSTTCS)","author":"Allender","year":"2021"},{"key":"ref22","first-page":"36:1","article-title":"On One-Way Functions from NP-Complete Problems","volume-title":"Proceedings of the Computational Complexity Conference (CCC)","author":"Liu","year":"2022"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-48615-9_8"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-38545-2_21"},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585138"},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585130"},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1109\/FSCS.1990.89604"},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(84)90070-9"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793244708"},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.1145\/100216.100269"},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.1007\/BF00196774"},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.1109\/SCT.1995.514853"},{"key":"ref33","first-page":"29:1","article-title":"Exact search-to-decision reductions for time-bounded kolmogorov complexity","volume-title":"Proceedings of the Computational Complexity Conference (CCC)","author":"Hirahara","year":"2024"},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.1070\/RM1970v025n06ABEH001269"},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.07.017"},{"key":"ref36","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(93)90204-M"},{"key":"ref37","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1995.1120"},{"key":"ref38","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451065"},{"key":"ref39","first-page":"26:1","article-title":"Symmetry of Information from Meta-Complexity","volume-title":"Proceedings of the Computational Complexity Conference (CCC)","author":"Hirahara","year":"2022"},{"key":"ref40","article-title":"A Simpler Proof of the Worst-Case to Average-Case Reduction for Polynomial Hierarchy via Symmetry of Information","volume":"007","author":"Goldberg","year":"2022","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"issue":"4","key":"ref41","doi-asserted-by":"crossref","first-page":"860","DOI":"10.1145\/502090.502099","article-title":"Extractors and pseudorandom generators","volume":"48","author":"Trevisan","year":"2001","journal-title":"J. ACM"},{"key":"ref42","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2002.1824"},{"key":"ref43","doi-asserted-by":"publisher","DOI":"10.1145\/1538902.1538904"},{"key":"ref44","article-title":"Optimal Coding for Randomized Kolmogorov Complexity and Its Applications","volume":"abs\/2409.12744","author":"Hirahara","year":"2024","journal-title":"CoRR"},{"key":"ref45","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.11.033"},{"key":"ref46","doi-asserted-by":"publisher","DOI":"10.1109\/MAHC.1984.10036"},{"key":"ref47","first-page":"10:1","article-title":"Learning Algorithms from Natural Proofs","volume-title":"Proceedings of the Conference on Computational Complexity (CCC)","author":"Carmosino","year":"2016"},{"key":"ref48","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00032"},{"key":"ref49","first-page":"31:1","article-title":"Connecting Perebor Conjectures: Towards a Search to Decision Reduction for Minimizing Formulas","volume-title":"Proceedings of the Computational Complexity Conference (CCC)","author":"Ilango","year":"2020"},{"key":"ref50","first-page":"34:1","article-title":"Search-to-decision reductions for kolmogorov complexity","volume-title":"Proceedings of the Computational Complexity Conference (CCC)","author":"Mazor","year":"2024"},{"key":"ref51","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00014"},{"key":"ref52","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-007-0053-2"},{"key":"ref53","first-page":"84:1","article-title":"Errorless Versus Error-Prone Average-Case Complexity","volume-title":"Proceedings of the Innovations in Theoretical Computer Science Conference (ITCS)","author":"Hirahara","year":"2022"},{"key":"ref54","first-page":"25:1","article-title":"Finding Errorless Pessiland in Error-Prone Heuristica","volume-title":"Proceedings of the Computational Complexity Conference (CCC)","author":"Hirahara","year":"2022"},{"key":"ref55","doi-asserted-by":"publisher","DOI":"10.1109\/sfcs.1982.45"},{"key":"ref56","doi-asserted-by":"publisher","DOI":"10.1561\/0400000010"},{"key":"ref57","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214051"},{"key":"ref58","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-84882-903-9"},{"key":"ref59","doi-asserted-by":"publisher","DOI":"10.1002\/047174882x"},{"key":"ref60","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63483"}],"event":{"name":"2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)","start":{"date-parts":[[2024,10,27]]},"location":"Chicago, IL, USA","end":{"date-parts":[[2024,10,30]]}},"container-title":["2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)"],"original-title":[],"link":[{"URL":"http:\/\/xplorestaging.ieee.org\/ielx8\/10755992\/10756014\/10756127.pdf?arnumber=10756127","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,30]],"date-time":"2024-11-30T05:53:01Z","timestamp":1732945981000},"score":1,"resource":{"primary":{"URL":"https:\/\/ieeexplore.ieee.org\/document\/10756127\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,27]]},"references-count":60,"URL":"https:\/\/doi.org\/10.1109\/focs61266.2024.00030","relation":{},"subject":[],"published":{"date-parts":[[2024,10,27]]}}}