{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,12]],"date-time":"2025-06-12T04:15:59Z","timestamp":1749701759356,"version":"3.41.0"},"reference-count":0,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGACT News"],"published-print":{"date-parts":[[2025,6,6]]},"abstract":"<jats:p>Meta-complexity refers to the study of the computational complexity of computing natural complexity measures, such as time-bounded Kolmogorov complexity and the minimal circuit size. Despite decades of interest, important basic questions about these problems remain unresolved.<\/jats:p>\n          <jats:p>This survey explores some of the recent connections between meta-complexity and cryptography, focusing on how tools from one domain can help solving long-standing questions in the other.<\/jats:p>","DOI":"10.1145\/3744715.3744722","type":"journal-article","created":{"date-parts":[[2025,6,11]],"date-time":"2025-06-11T23:38:13Z","timestamp":1749685093000},"page":"63-101","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Guest Column: On Cryptography and Meta-Complexity"],"prefix":"10.1145","volume":"56","author":[{"given":"Noam","family":"Mazor","sequence":"first","affiliation":[{"name":"Tel Aviv University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rafael","family":"Pass","sequence":"additional","affiliation":[{"name":"Cornell Tech, Technion, and Tel Aviv University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,6,11]]},"container-title":["ACM SIGACT News"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3744715.3744722","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,11]],"date-time":"2025-06-11T23:38:14Z","timestamp":1749685094000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3744715.3744722"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,6]]},"references-count":0,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,6,6]]}},"alternative-id":["10.1145\/3744715.3744722"],"URL":"https:\/\/doi.org\/10.1145\/3744715.3744722","relation":{},"ISSN":["0163-5700"],"issn-type":[{"value":"0163-5700","type":"print"}],"subject":[],"published":{"date-parts":[[2025,6,6]]},"assertion":[{"value":"2025-06-11","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}