{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:05:34Z","timestamp":1781028334394,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":60,"publisher":"ACM","license":[{"start":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T00:00:00Z","timestamp":1780963200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2026,6,9]]},"DOI":"10.1145\/3798129.3800780","type":"proceedings-article","created":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:53:56Z","timestamp":1781027636000},"page":"641-652","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Kolmogorov\u2019s Approach to P vs. NP: Chain Rules for Time-Bounded Kolmogorov Complexity"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0002-2861-017X","authenticated-orcid":false,"given":"Valentine","family":"Kabanets","sequence":"first","affiliation":[{"name":"Simon Fraser University, Computing Science, Burnaby, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-9899-1147","authenticated-orcid":false,"given":"Antonina","family":"Kolokolova","sequence":"additional","affiliation":[{"name":"Memorial University of Newfoundland, St John's, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,6,9]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Learning with Distributional Inverters. In International Conference on Algorithmic Learning Theory","volume":"106","author":"Binnendyk Eric","year":"2022","unstructured":"Eric Binnendyk, Marco Carmosino, Antonina Kolokolova, R. Ramyaa, and Manuel Sabin. 2022. Learning with Distributional Inverters. In International Conference on Algorithmic Learning Theory, 29 March - 1 April 2022, Paris, France, Sanjoy Dasgupta and Nika Haghtalab (Eds.) (Proceedings of Machine Learning Research, Vol. 167). PMLR, 90\u2013106. https:\/\/proceedings.mlr.press\/v167\/binnendyk22a.html"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/S00037-005-0199-5"},{"key":"e_1_3_2_1_3_1","volume-title":"Conference on Computational Complexity (CCC). 10:1\u201310:24","author":"Carmosino Marco L.","year":"2016","unstructured":"Marco L. Carmosino, Russell Impagliazzo, Valentine Kabanets, and Antonina Kolokolova. 2016. Learning Algorithms from Natural Proofs. In Conference on Computational Complexity (CCC). 10:1\u201310:24."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.APPROX-RANDOM.2017.35"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2022.45"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.APPROX\/RANDOM.2023.65"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488667"},{"key":"e_1_3_2_1_8_1","volume-title":"TR22-007","author":"Goldberg Halley","year":"2022","unstructured":"Halley Goldberg and Valentine Kabanets. 2022. A Simpler Proof of the Worst-Case to Average-Case Reduction for Polynomial Hierarchy via Symmetry of Information. Electron. Colloquium Comput. Complex., TR22-007 (2022), ECCC:TR22-007. https:\/\/eccc.weizmann.ac.il\/report\/2022\/007"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.CCC.2023.12"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.CCC.2022.16"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","unstructured":"Oded Goldreich. 2011. In a World of P=BPP. In Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation - In Collaboration with Lidor Avigad Mihir Bellare Zvika Brakerski Shafi Goldwasser Shai Halevi Tali Kaufman Leonid Levin Noam Nisan Dana Ron Madhu Sudan Luca Trevisan Salil Vadhan Avi Wigderson David Zuckerman Oded Goldreich (Ed.) (Lecture Notes in Computer Science Vol. 6650). Springer 191\u2013232. https:\/\/doi.org\/10.1007\/978-3-642-22670-0_20 10.1007\/978-3-642-22670-0_20","DOI":"10.1007\/978-3-642-22670-0_20"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.APPROX\/RANDOM.2022.20"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00032"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00014"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.CCC.2020.20"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384251"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451065"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2022.26"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585130"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585138"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.CCC.2024.29"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00078"},{"key":"e_1_3_2_1_23_1","volume-title":"TR25-092","author":"Hirahara Shuichi","year":"2025","unstructured":"Shuichi Hirahara and Mikito Nanashima. 2025. Complexity-Theoretic Inductive Inference. Electron. Colloquium Comput. Complex., TR25-092 (2025), ECCC:TR25-092. https:\/\/eccc.weizmann.ac.il\/report\/2025\/092"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585154"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS57990.2023.00048"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585187"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3520051"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/S00037-023-00241-0"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(02)00024-7"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258590"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/J.APAL.2003.12.003"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/exm017"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335314"},{"key":"e_1_3_2_1_34_1","volume-title":"TR25-089","author":"Kabanets Valentine","year":"2025","unstructured":"Valentine Kabanets and Antonina Kolokolova. 2025. Kolmogorov\u2019s Approach to P vs NP: Chain Rules for Time-Bounded Kolmogorov Complexity. Electron. Colloquium Comput. Complex., TR25-089 (2025), ECCC:TR25-089. https:\/\/eccc.weizmann.ac.il\/report\/2025\/089\/##revision1"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ITCS.2024.68"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ITCS.2021.44"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/0220059"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00051"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.2307\/2687774"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.2178\/JSL\/1080938841"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/J.TCS.2005.07.017"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1023\/A"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS61266.2024.00095"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-11298-1"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00118"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.CCC.2022.36"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-78011-0_8"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(93)90204-M"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1995.1120"},{"key":"e_1_3_2_1_50_1","volume-title":"Oliveira","author":"Lu Zhenjian","year":"2022","unstructured":"Zhenjian Lu and Igor C. Oliveira. 2022. Theory and Applications of Probabilistic Kolmogorov Complexity. Bull. EATCS, 137 (2022), http:\/\/bulletin.eatcs.org\/index.php\/beatcs\/article\/view\/700"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ICALP.2024.110"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80043-1"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.CCC.2017.18"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-74510-5_32"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1006\/JCSS.2002.1824"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1006\/JCSS.1997.1494"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00067"},{"key":"e_1_3_2_1_58_1","volume-title":"Kolmogorov Complexity and Derandomization. Ph. D. Dissertation","author":"Ronneburger Detlef","unstructured":"Detlef Ronneburger. 2004. Kolmogorov Complexity and Derandomization. Ph. D. Dissertation. Rutgers University."},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502099"},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1070\/RM1970v025n06ABEH001269"}],"event":{"name":"STOC '26: 58th Annual ACM Symposium on Theory of Computing","location":"Salt Lake City UT USA","acronym":"STOC '26","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 58th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3798129.3800780","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:56:34Z","timestamp":1781027794000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3798129.3800780"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,9]]},"references-count":60,"alternative-id":["10.1145\/3798129.3800780","10.1145\/3798129"],"URL":"https:\/\/doi.org\/10.1145\/3798129.3800780","relation":{},"subject":[],"published":{"date-parts":[[2026,6,9]]},"assertion":[{"value":"2026-06-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}