{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,20]],"date-time":"2026-01-20T11:47:17Z","timestamp":1768909637070,"version":"3.49.0"},"publisher-location":"New York, NY, USA","reference-count":50,"publisher":"ACM","license":[{"start":{"date-parts":[[2023,6,2]],"date-time":"2023-06-02T00:00:00Z","timestamp":1685664000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["CCF-1909429"],"award-info":[{"award-number":["CCF-1909429"]}]},{"DOI":"10.13039\/501100000288","name":"Royal Society","doi-asserted-by":"publisher","award":["URF\\R1\\19105"],"award-info":[{"award-number":["URF\\R1\\19105"]}],"id":[{"id":"10.13039\/501100000288","id-type":"DOI","asserted-by":"publisher"}]},{"name":"EPSRC","award":["EP\/V048201\/1"],"award-info":[{"award-number":["EP\/V048201\/1"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2023,6,2]]},"DOI":"10.1145\/3564246.3585138","type":"proceedings-article","created":{"date-parts":[[2023,5,16]],"date-time":"2023-05-16T17:34:20Z","timestamp":1684258460000},"page":"1039-1050","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["A Duality between One-Way Functions and Average-Case Symmetry of Information"],"prefix":"10.1145","author":[{"given":"Shuichi","family":"Hirahara","sequence":"first","affiliation":[{"name":"National Institute of Informatics, Japan"}]},{"given":"Rahul","family":"Ilango","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}]},{"given":"Zhenjian","family":"Lu","sequence":"additional","affiliation":[{"name":"University of Oxford, UK"}]},{"given":"Mikito","family":"Nanashima","sequence":"additional","affiliation":[{"name":"Tokyo Institute of Technology, Japan"}]},{"given":"Igor C.","family":"Oliveira","sequence":"additional","affiliation":[{"name":"University of Warwick, UK"}]}],"member":"320","published-online":{"date-parts":[[2023,6,2]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.53733\/148"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/050628994"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2009.12"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000004"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753979834388X"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2000.856742"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-005-0199-5"},{"key":"e_1_3_2_1_8_1","first-page":"1","article-title":"A Simpler Proof of the Worst-Case to Average-Case Reduction for Polynomial Hierarchy via Symmetry of Information","volume":"7","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. , 7 (2022), 1 \u2013 14 . https:\/\/eccc.weizmann.ac.il\/report\/2022\/007\/ 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., 7 (2022), 1\u201314. https:\/\/eccc.weizmann.ac.il\/report\/2022\/007\/","journal-title":"Electron. Colloquium Comput. Complex."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2022.16"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(90)90010-U"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546891"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(84)90070-9"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793244708"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00032"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451065"},{"key":"e_1_3_2_1_16_1","volume-title":"Meta-Computational Average-Case Complexity: A New Paradigm Toward Excluding Heuristica. Bull. EATCS, 136","author":"Hirahara Shuichi","year":"2022","unstructured":"Shuichi Hirahara . 2022. Meta-Computational Average-Case Complexity: A New Paradigm Toward Excluding Heuristica. Bull. EATCS, 136 ( 2022 ), http:\/\/bulletin.eatcs.org\/index.php\/beatcs\/article\/view\/688 Shuichi Hirahara. 2022. Meta-Computational Average-Case Complexity: A New Paradigm Toward Excluding Heuristica. Bull. EATCS, 136 (2022), http:\/\/bulletin.eatcs.org\/index.php\/beatcs\/article\/view\/688"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2022.26"},{"key":"e_1_3_2_1_18_1","volume-title":"Oliveira","author":"Hirahara Shuichi","year":"2023","unstructured":"Shuichi Hirahara , Rahul Ilango , Zhenjian Lu , Mikito Nanashima , and Igor C . Oliveira . 2023 . A Duality Between One-Way Functions and Average-Case Symmetry of Information. Cryptology ePrint Archive, Paper 2023\/424. https:\/\/eprint.iacr.org\/2023\/424 Shuichi Hirahara, Rahul Ilango, Zhenjian Lu, Mikito Nanashima, and Igor C. Oliveira. 2023. A Duality Between One-Way Functions and Average-Case Symmetry of Information. Cryptology ePrint Archive, Paper 2023\/424. https:\/\/eprint.iacr.org\/2023\/424"},{"key":"e_1_3_2_1_19_1","unstructured":"Rahul Ilango Hanlin Ren and Rahul Santhanam. 2021. Hardness on any Samplable Distribution Suffices: New Characterizations of One-Way Functions by Meta-Complexity. Electron. Colloquium Comput. Complex. 82. https:\/\/eccc.weizmann.ac.il\/report\/2021\/082 \t\t\t\t  Rahul Ilango Hanlin Ren and Rahul Santhanam. 2021. Hardness on any Samplable Distribution Suffices: New Characterizations of One-Way Functions by Meta-Complexity. Electron. Colloquium Comput. Complex. 82. https:\/\/eccc.weizmann.ac.il\/report\/2021\/082"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/FSCS.1990.89604"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63483"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/0220059"},{"key":"e_1_3_2_1_23_1","volume-title":"Three approaches to the quantitative definition of information. Problems of information transmission, 1, 1","author":"Kolmogorov Andrey N.","year":"1965","unstructured":"Andrey N. Kolmogorov . 1965. Three approaches to the quantitative definition of information. Problems of information transmission, 1, 1 ( 1965 ), 1\u20137. Andrey N. Kolmogorov. 1965. Three approaches to the quantitative definition of information. Problems of information transmission, 1, 1 (1965), 1\u20137."},{"key":"e_1_3_2_1_24_1","volume-title":"Soc. meeting on 10\/31\/67)","author":"Kolmogorov Andrey N.","year":"1968","unstructured":"Andrey N. Kolmogorov . 1968 . Several Theorems about Algorithmic Entropy and Algorithmic Amount of Information (a talk at a Moscow Math . Soc. meeting on 10\/31\/67) . In Usp. Mat. Nauk. 23, 201. Andrey N. Kolmogorov. 1968. Several Theorems about Algorithmic Entropy and Algorithmic Amount of Information (a talk at a Moscow Math. Soc. meeting on 10\/31\/67). In Usp. Mat. Nauk. 23, 201."},{"key":"e_1_3_2_1_25_1","volume-title":"Kolmogorov complexity and formula lower bounds. Ph. D. Dissertation","author":"Lee Troy","unstructured":"Troy Lee . 2006. Kolmogorov complexity and formula lower bounds. Ph. D. Dissertation . University of Amsterdam. Troy Lee. 2006. Kolmogorov complexity and formula lower bounds. Ph. D. Dissertation. University of Amsterdam."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.07.017"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-11298-1"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00118"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-84242-0_2"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2022.36"},{"key":"e_1_3_2_1_31_1","volume-title":"Resource bounded Kolmogorov complexity, a link between computational complexity and information theory. Ph. D. Dissertation","author":"Longpr\u00e9 Luc","unstructured":"Luc Longpr\u00e9 . 1986. Resource bounded Kolmogorov complexity, a link between computational complexity and information theory. Ph. D. Dissertation . Cornell University . Luc Longpr\u00e9. 1986. Resource bounded Kolmogorov complexity, a link between computational complexity and information theory. Ph. D. Dissertation. Cornell University."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(93)90204-M"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1995.1120"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2021.94"},{"key":"e_1_3_2_1_35_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 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_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451085"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2022.92"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00196774"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2019.32"},{"key":"e_1_3_2_1_40_1","volume-title":"Computational Complexity Conference (CCC). 27:1\u201327:29","author":"Oliveira Igor C.","year":"2019","unstructured":"Igor C. Oliveira , J\u00e1n Pich , and Rahul Santhanam . 2019 . Hardness Magnification near State-Of-The-Art Lower Bounds . In Computational Complexity Conference (CCC). 27:1\u201327:29 . https:\/\/theoryofcomputing.org\/articles\/v017a011\/ Igor C. Oliveira, J\u00e1n Pich, and Rahul Santhanam. 2019. Hardness Magnification near State-Of-The-Art Lower Bounds. In Computational Complexity Conference (CCC). 27:1\u201327:29. https:\/\/theoryofcomputing.org\/articles\/v017a011\/"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2002.1824"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2021.35"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/100216.100269"},{"key":"e_1_3_2_1_44_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 . Detlef Ronneburger. 2004. Kolmogorov Complexity and Derandomization. Ph. D. Dissertation. Rutgers University."},{"key":"e_1_3_2_1_45_1","volume-title":"Kolmogorov complexity and algorithmic randomness","author":"Shen Alexander","unstructured":"Alexander Shen , Vladimir A. Uspensky , and Nikolay Vereshchagin . 2017. Kolmogorov complexity and algorithmic randomness . American Mathematical Society . Alexander Shen, Vladimir A. Uspensky, and Nikolay Vereshchagin. 2017. Kolmogorov complexity and algorithmic randomness. American Mathematical Society."},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/800061.808762"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-007-0233-x"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000010"},{"key":"e_1_3_2_1_49_1","unstructured":"Osamu Watanabe. 2022. Personal Communication. \t\t\t\t  Osamu Watanabe. 2022. Personal Communication."},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1070\/RM1970v025n06ABEH001269"}],"event":{"name":"STOC '23: 55th Annual ACM Symposium on Theory of Computing","location":"Orlando FL USA","acronym":"STOC '23","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 55th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3564246.3585138","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3564246.3585138","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:17:27Z","timestamp":1750295847000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3564246.3585138"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,2]]},"references-count":50,"alternative-id":["10.1145\/3564246.3585138","10.1145\/3564246"],"URL":"https:\/\/doi.org\/10.1145\/3564246.3585138","relation":{},"subject":[],"published":{"date-parts":[[2023,6,2]]},"assertion":[{"value":"2023-06-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}