{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:22:24Z","timestamp":1750220544103,"version":"3.41.0"},"reference-count":69,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2021,3,16]],"date-time":"2021-03-16T00:00:00Z","timestamp":1615852800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGACT News"],"published-print":{"date-parts":[[2021,3,16]]},"abstract":"<jats:p>We review a study of average-case complexity through the lens of interactive puzzles- interactive games between a computationally bounded Challenger and computationally-bounded Solver\/Attacker. Most notably, we use this treatment to review a recent result showing that if NP is hard-on-the-average, then there exists a sampleable distribution over only true statements of an NP language, for which no probabilistic polynomial time algorithm can find witnesses. We also discuss connections to the problem of whether average-case hardness in NP implies averagecase hardness in TFNP, or the existence of cryptographic one-way functions.<\/jats:p>","DOI":"10.1145\/3457588.3457598","type":"journal-article","created":{"date-parts":[[2021,3,16]],"date-time":"2021-03-16T22:06:51Z","timestamp":1615932411000},"page":"47-69","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Guest Column"],"prefix":"10.1145","volume":"52","author":[{"given":"R.","family":"Pass","sequence":"first","affiliation":[{"name":"Cornell Tech, New York, NY, USA"}]},{"given":"M.","family":"Venkitasubramaniam","sequence":"additional","affiliation":[{"name":"University of Rochester, Rochester, NY, USA"}]}],"member":"320","published-online":{"date-parts":[[2021,3,16]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_2_1_1_1","DOI":"10.1145\/1132516.1132614"},{"doi-asserted-by":"publisher","key":"e_1_2_1_2_1","DOI":"10.1007\/BF01275486"},{"doi-asserted-by":"publisher","key":"e_1_2_1_3_1","DOI":"10.1016\/0022-0000(88)90028-1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_4_1","DOI":"10.5555\/646766.704152"},{"doi-asserted-by":"publisher","key":"e_1_2_1_5_1","DOI":"10.5555\/1328738.1328740"},{"doi-asserted-by":"publisher","key":"e_1_2_1_6_1","DOI":"10.1016\/0022-0000(92)90019-F"},{"doi-asserted-by":"publisher","key":"e_1_2_1_7_1","DOI":"10.1007\/978-3-662-46494-6_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_8_1","DOI":"10.5555\/946243.946341"},{"doi-asserted-by":"publisher","key":"e_1_2_1_9_1","DOI":"10.1109\/TIT.1983.1056754"},{"doi-asserted-by":"publisher","key":"e_1_2_1_10_1","DOI":"10.1145\/321526.321530"},{"doi-asserted-by":"publisher","key":"e_1_2_1_11_1","DOI":"10.1145\/1516512.1516516"},{"doi-asserted-by":"publisher","key":"e_1_2_1_12_1","DOI":"10.1007\/978-3-642-11799-2_2"},{"key":"e_1_2_1_13_1","first-page":"229","volume-title":"TCC 2015, Warsaw, Poland, March 23--25, 2015, Proceedings, Part II","author":"Chung Kai-Min","year":"2015"},{"doi-asserted-by":"publisher","key":"e_1_2_1_14_1","DOI":"10.1145\/1461928.1461951"},{"doi-asserted-by":"publisher","key":"e_1_2_1_15_1","DOI":"10.5555\/2133036.2133098"},{"doi-asserted-by":"publisher","key":"e_1_2_1_16_1","DOI":"10.1109\/TIT.1976.1055638"},{"doi-asserted-by":"publisher","key":"e_1_2_1_17_1","DOI":"10.1016\/S0019-9958(84)80056-X"},{"doi-asserted-by":"publisher","key":"e_1_2_1_18_1","DOI":"10.5555\/646234.682556"},{"doi-asserted-by":"publisher","key":"e_1_2_1_19_1","DOI":"10.1137\/0222061"},{"key":"e_1_2_1_20_1","first-page":"429","article-title":"On completeness and soundness in interactive proof systems","volume":"5","author":"F\u00a8urer Martin","year":"1989","journal-title":"Advances in Computing Research"},{"doi-asserted-by":"publisher","key":"e_1_2_1_21_1","DOI":"10.1145\/1993636.1993651"},{"doi-asserted-by":"publisher","key":"e_1_2_1_22_1","DOI":"10.5555\/1102023"},{"volume-title":"Towards a unified complexity theory of total functions. Unpublished manuscript","year":"2016","author":"Goldberg Paul W.","key":"e_1_2_1_23_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_24_1","DOI":"10.5555\/519078"},{"doi-asserted-by":"publisher","key":"e_1_2_1_25_1","DOI":"10.5555\/2168303.2168315"},{"doi-asserted-by":"publisher","key":"e_1_2_1_26_1","DOI":"10.5555\/19478.19500"},{"doi-asserted-by":"publisher","key":"e_1_2_1_27_1","DOI":"10.1145\/116825.116852"},{"doi-asserted-by":"publisher","key":"e_1_2_1_28_1","DOI":"10.1016\/0022-0000(84)90070-9"},{"doi-asserted-by":"publisher","key":"e_1_2_1_29_1","DOI":"10.1137\/0218012"},{"doi-asserted-by":"publisher","key":"e_1_2_1_30_1","DOI":"10.5555\/1884265.1884282"},{"volume-title":"Logic in Computer Science Column, The Bulletin of EATCS.","year":"1989","author":"Gurevich Yuri","key":"e_1_2_1_31_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_32_1","DOI":"10.1016\/0022-0000(91)90007-R"},{"doi-asserted-by":"publisher","key":"e_1_2_1_33_1","DOI":"10.1109\/CCC.2010.17"},{"doi-asserted-by":"publisher","key":"e_1_2_1_34_1","DOI":"10.1109\/SFCS.1983.21"},{"doi-asserted-by":"publisher","key":"e_1_2_1_35_1","DOI":"10.1137\/S0097539793244708"},{"doi-asserted-by":"publisher","key":"e_1_2_1_36_1","DOI":"10.1007\/978-3-642-11799-2_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_37_1","DOI":"10.1007\/978-3-030-64381-2_22"},{"volume-title":"8th Innovations in Theoretical Computer Science Conference, ITCS 2017","year":"2017","author":"Hub'avcek Pavel","key":"e_1_2_1_38_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_39_1","DOI":"10.5555\/829497.829786"},{"doi-asserted-by":"publisher","key":"e_1_2_1_40_1","DOI":"10.1109\/FSCS.1990.89604"},{"doi-asserted-by":"publisher","key":"e_1_2_1_41_1","DOI":"10.1109\/SFCS.1989.63483"},{"doi-asserted-by":"publisher","key":"e_1_2_1_42_1","DOI":"10.1145\/258533.258590"},{"doi-asserted-by":"publisher","key":"e_1_2_1_43_1","DOI":"10.1109\/SFCS.1985.31"},{"doi-asserted-by":"publisher","key":"e_1_2_1_44_1","DOI":"10.5555\/39528.39530"},{"doi-asserted-by":"publisher","key":"e_1_2_1_45_1","DOI":"10.1080\/00207166808803030"},{"doi-asserted-by":"publisher","key":"e_1_2_1_46_1","DOI":"10.1109\/FOCS.2014.47"},{"doi-asserted-by":"publisher","key":"e_1_2_1_47_1","DOI":"10.1137\/0215020"},{"doi-asserted-by":"publisher","key":"e_1_2_1_48_1","DOI":"10.1109\/FOCS46700.2020.00118"},{"key":"e_1_2_1_49_1","first-page":"301","volume-title":"Innovations in Computer Science - ICS","author":"Livne Noam","year":"2010"},{"doi-asserted-by":"publisher","key":"e_1_2_1_50_1","DOI":"10.1145\/146585.146605"},{"doi-asserted-by":"publisher","key":"e_1_2_1_51_1","DOI":"10.1016\/0304-3975(91)90200-L"},{"doi-asserted-by":"publisher","key":"e_1_2_1_52_1","DOI":"10.1007\/s00037-005-0197-7"},{"key":"e_1_2_1_53_1","first-page":"96","volume-title":"23rd Annual International Cryptology Conference, Santa Barbara, California, USA, August 17--21, 2003","author":"Naor Moni","year":"2003"},{"doi-asserted-by":"publisher","key":"e_1_2_1_54_1","DOI":"10.1145\/73007.73011"},{"doi-asserted-by":"publisher","key":"e_1_2_1_55_1","DOI":"10.1016\/S0022-0000(05)80043-1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_56_1","DOI":"10.1109\/ISTCS.1993.253489"},{"doi-asserted-by":"publisher","key":"e_1_2_1_57_1","DOI":"10.1016\/S0022-0000(05)80063-7"},{"doi-asserted-by":"publisher","key":"e_1_2_1_58_1","DOI":"10.1145\/1993636.1993652"},{"doi-asserted-by":"publisher","key":"e_1_2_1_59_1","DOI":"10.1145\/2382559.2382561"},{"volume-title":"IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS)","year":"2020","author":"Pass Rafael","key":"e_1_2_1_60_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_61_1","DOI":"10.1137\/S0097539795280895"},{"doi-asserted-by":"publisher","key":"e_1_2_1_62_1","DOI":"10.1145\/100216.100269"},{"doi-asserted-by":"crossref","unstructured":"Alon\n      Rosen Gil\n      Segev and \n      Ido\n      Shahaf\n    .\n  Can PPAD hardness be based on standard cryptographic assumptions? In Yael Kalai and Leonid Reyzin editors Theory of Cryptography - 15th International Conference TCC \n  2017 Baltimore MD USA November 12--15 2017 Proceedings Part II volume \n  10678\n   of \n  Lecture Notes in Computer Science pages \n  747\n  --\n  776\n  . \n  Springer 2017.  Alon Rosen Gil Segev and Ido Shahaf. Can PPAD hardness be based on standard cryptographic assumptions? In Yael Kalai and Leonid Reyzin editors Theory of Cryptography - 15th International Conference TCC 2017 Baltimore MD USA November 12--15 2017 Proceedings Part II volume 10678 of Lecture Notes in Computer Science pages 747--776. Springer 2017.","key":"e_1_2_1_63_1","DOI":"10.1007\/978-3-319-70503-3_25"},{"doi-asserted-by":"publisher","key":"e_1_2_1_65_1","DOI":"10.1145\/146585.146609"},{"doi-asserted-by":"publisher","key":"e_1_2_1_66_1","DOI":"10.1145\/800061.808762"},{"doi-asserted-by":"publisher","key":"e_1_2_1_67_1","DOI":"10.1016\/S0019-9958(64)90223-2"},{"doi-asserted-by":"publisher","key":"e_1_2_1_68_1","DOI":"10.1109\/MAHC.1984.10036"},{"doi-asserted-by":"publisher","key":"e_1_2_1_69_1","DOI":"10.1016\/S0019-9958(67)90401-9"},{"doi-asserted-by":"publisher","key":"e_1_2_1_70_1","DOI":"10.1007\/11681878_22"}],"container-title":["ACM SIGACT News"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3457588.3457598","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3457588.3457598","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:28:07Z","timestamp":1750195687000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3457588.3457598"}},"subtitle":["Average-case Complexity Through the Lens of Interactive Puzzles"],"short-title":[],"issued":{"date-parts":[[2021,3,16]]},"references-count":69,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,3,16]]}},"alternative-id":["10.1145\/3457588.3457598"],"URL":"https:\/\/doi.org\/10.1145\/3457588.3457598","relation":{},"ISSN":["0163-5700"],"issn-type":[{"type":"print","value":"0163-5700"}],"subject":[],"published":{"date-parts":[[2021,3,16]]},"assertion":[{"value":"2021-03-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}