{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T16:06:29Z","timestamp":1750694789570,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":39,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,6,9]],"date-time":"2022-06-09T00:00:00Z","timestamp":1654732800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/linproxy.fan.workers.dev:443\/https\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,6,9]]},"DOI":"10.1145\/3519935.3520041","type":"proceedings-article","created":{"date-parts":[[2022,6,10]],"date-time":"2022-06-10T15:29:32Z","timestamp":1654874972000},"page":"1566-1574","update-policy":"https:\/\/linproxy.fan.workers.dev:443\/https\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Worst-case to average-case reductions via additive combinatorics"],"prefix":"10.1145","author":[{"given":"Vahid R.","family":"Asadi","sequence":"first","affiliation":[{"name":"University of Waterloo, Canada"}]},{"given":"Alexander","family":"Golovnev","sequence":"additional","affiliation":[{"name":"Georgetown University, USA"}]},{"given":"Tom","family":"Gur","sequence":"additional","affiliation":[{"name":"University of Warwick, UK"}]},{"given":"Igor","family":"Shinkar","sequence":"additional","affiliation":[{"name":"Simon Fraser University, Canada"}]}],"member":"320","published-online":{"date-parts":[[2022,6,10]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237838"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258604"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.32"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Vahid R. Asadi Alexander Golovnev Tom Gur and Igor Shinkar. 2022. Worst-Case to Average-Case Reductions via Additive Combinatorics. Electronic Colloquium on Computational Complexity https:\/\/linproxy.fan.workers.dev:443\/https\/eccc.weizmann.ac.il\/report\/2022\/020  Vahid R. Asadi Alexander Golovnev Tom Gur and Igor Shinkar. 2022. Worst-Case to Average-Case Reductions via Additive Combinatorics. Electronic Colloquium on Computational Complexity https:\/\/linproxy.fan.workers.dev:443\/https\/eccc.weizmann.ac.il\/report\/2022\/020","DOI":"10.1145\/3519935.3520041"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01275486"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055466"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-96884-1_26"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(92)90019-F"},{"key":"e_1_3_2_1_9_1","volume-title":"Sampling-Based Proofs of Almost-Periodicity Results and Algorithmic Applications. In ICALP","author":"Ben-Sasson Eli","year":"2014","unstructured":"Eli Ben-Sasson , Noga Ron-Zewi , Madhur Tulsiani , and Julia Wolf . 2014 . Sampling-Based Proofs of Almost-Periodicity Results and Algorithmic Applications. In ICALP 2014. 955\u2013966. Eli Ben-Sasson, Noga Ron-Zewi, Madhur Tulsiani, and Julia Wolf. 2014. Sampling-Based Proofs of Almost-Periodicity Results and Algorithmic Applications. In ICALP 2014. 955\u2013966."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/100216.100225"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000004"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00078"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188830"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188874"},{"key":"e_1_3_2_1_15_1","volume-title":"FOCS","author":"Clifford Raphael","year":"2015","unstructured":"Raphael Clifford , Allan Gr\u00f8nlund , and Kasper Green Larsen . 2015 . New unconditional hardness results for dynamic and online problems . In FOCS 2015. 1089\u20131107. Raphael Clifford, Allan Gr\u00f8nlund, and Kasper Green Larsen. 2015. New unconditional hardness results for dynamic and online problems. In FOCS 2015. 1089\u20131107."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00077"},{"key":"e_1_3_2_1_17_1","volume-title":"Data Structures Lower Bounds and Popular Conjectures. In ESA","author":"Dvo\u0159\u00e1k Pavel","year":"2021","unstructured":"Pavel Dvo\u0159\u00e1k , Michal Kouck\u1ef3 , Karel Kr\u00e1l , and Veronika Sl\u00edvov\u00e1 . 2021 . Data Structures Lower Bounds and Popular Conjectures. In ESA 2021. Pavel Dvo\u0159\u00e1k, Michal Kouck\u1ef3, Karel Kr\u00e1l, and Veronika Sl\u00edvov\u00e1. 2021. Data Structures Lower Bounds and Popular Conjectures. In ESA 2021."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/0222061"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.2001.3046"},{"volume-title":"Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation","author":"Goldreich Oded","key":"e_1_3_2_1_20_1","unstructured":"Oded Goldreich . 2011. Notes on Levin\u2019s Theory of Average-Case Complexity . In Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation . Springer , 233\u2013247. Oded Goldreich. 2011. Notes on Levin\u2019s Theory of Average-Case Complexity. In Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation. Springer, 233\u2013247."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00017"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746609"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"crossref","unstructured":"Monika Henzinger Andrea Lincoln and Barna Saha. 2021. The Complexity of Average-Case Dynamic Subgraph Counting. Electronic Colloquium on Computational Complexity.  Monika Henzinger Andrea Lincoln and Barna Saha. 2021. The Complexity of Average-Case Dynamic Subgraph Counting. Electronic Colloquium on Computational Complexity.","DOI":"10.1137\/1.9781611977073.23"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/SCT.1995.514853"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2011.34"},{"key":"e_1_3_2_1_26_1","volume-title":"FOCS","author":"Impagliazzo Russell","year":"1990","unstructured":"Russell Impagliazzo and Leonid A. Levin . 1990. No Better Ways to Generate Hard NP Instances than Picking Uniformly at Random . In FOCS 1990 . IEEE. Russell Impagliazzo and Leonid A. Levin. 1990. No Better Ways to Generate Hard NP Instances than Picking Uniformly at Random. In FOCS 1990. IEEE."},{"key":"e_1_3_2_1_27_1","volume-title":"FOCS","author":"Kiran","year":"2008","unstructured":"Kiran S. Kedlaya and Christopher Umans. 2008. Fast modular composition in any characteristic . In FOCS 2008 . 146\u2013155. Kiran S. Kedlaya and Christopher Umans. 2008. Fast modular composition in any characteristic. In FOCS 2008. 146\u2013155."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.21"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.142"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-26954-8_20"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215020"},{"key":"e_1_3_2_1_32_1","volume-title":"New directions in testing. Distributed computing and cryptography, 2","author":"Lipton Richard","year":"1991","unstructured":"Richard Lipton . 1991. New directions in testing. Distributed computing and cryptography, 2 ( 1991 ), 191\u2013202. Richard Lipton. 1991. New directions in testing. Distributed computing and cryptography, 2 (1991), 191\u2013202."},{"key":"e_1_3_2_1_33_1","volume-title":"An Exposition of Sanders\u2019 Quasi-Polynomial Freiman-Ruzsa Theorem. Theory of Computing, 1\u201314","author":"Lovett Shachar","year":"2015","unstructured":"Shachar Lovett . 2015 . An Exposition of Sanders\u2019 Quasi-Polynomial Freiman-Ruzsa Theorem. Theory of Computing, 1\u201314 . Shachar Lovett. 2015. An Exposition of Sanders\u2019 Quasi-Polynomial Freiman-Ruzsa Theorem. Theory of Computing, 1\u201314."},{"key":"e_1_3_2_1_34_1","unstructured":"Shachar Lovett. 2017. Additive combinatorics and its applications in theoretical computer science. Theory of Computing 1\u201355.  Shachar Lovett. 2017. Additive combinatorics and its applications in theoretical computer science. Theory of Computing 1\u201355."},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1039488.1039490"},{"key":"e_1_3_2_1_36_1","first-page":"627","article-title":"On the Bogolyubov\u2013Ruzsa lemma","volume":"5","author":"Sanders Tom","year":"2012","unstructured":"Tom Sanders . 2012 . On the Bogolyubov\u2013Ruzsa lemma . IEEE Transactions on Information Theory , 5 , 3 (2012), 627 \u2013 655 . Tom Sanders. 2012. On the Bogolyubov\u2013Ruzsa lemma. IEEE Transactions on Information Theory, 5, 3 (2012), 627\u2013655.","journal-title":"IEEE Transactions on Information Theory"},{"volume-title":"A computational introduction to number theory and algebra","author":"Shoup Victor","key":"e_1_3_2_1_37_1","unstructured":"Victor Shoup . 2009. A computational introduction to number theory and algebra . Cambridge . Victor Shoup. 2009. A computational introduction to number theory and algebra. Cambridge."},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1730"},{"key":"e_1_3_2_1_39_1","volume-title":"ICM","author":"Williams Virginia Vassilevska","year":"2018","unstructured":"Virginia Vassilevska Williams . 2018 . On some fine-grained questions in algorithms and complexity . In ICM 2018. World Scientific. Virginia Vassilevska Williams. 2018. On some fine-grained questions in algorithms and complexity. In ICM 2018. World Scientific."}],"event":{"name":"STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Rome Italy","acronym":"STOC '22"},"container-title":["Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/linproxy.fan.workers.dev:443\/https\/dl.acm.org\/doi\/10.1145\/3519935.3520041","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/linproxy.fan.workers.dev:443\/https\/dl.acm.org\/doi\/pdf\/10.1145\/3519935.3520041","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:31:15Z","timestamp":1750188675000},"score":1,"resource":{"primary":{"URL":"https:\/\/linproxy.fan.workers.dev:443\/https\/dl.acm.org\/doi\/10.1145\/3519935.3520041"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,9]]},"references-count":39,"alternative-id":["10.1145\/3519935.3520041","10.1145\/3519935"],"URL":"https:\/\/linproxy.fan.workers.dev:443\/https\/doi.org\/10.1145\/3519935.3520041","relation":{},"subject":[],"published":{"date-parts":[[2022,6,9]]},"assertion":[{"value":"2022-06-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}