{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:54:19Z","timestamp":1781078059213,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":37,"publisher":"ACM","license":[{"start":{"date-parts":[[2024,6,10]],"date-time":"2024-06-10T00:00:00Z","timestamp":1717977600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Alfred P. Sloan Foundation","award":["G-2020-13941"],"award-info":[{"award-number":["G-2020-13941"]}]},{"name":"Simons Investigator Award","award":[""],"award-info":[{"award-number":[""]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2024,6,10]]},"DOI":"10.1145\/3618260.3649748","type":"proceedings-article","created":{"date-parts":[[2024,6,11]],"date-time":"2024-06-11T19:25:02Z","timestamp":1718133902000},"page":"1071-1082","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Complexity-Theoretic Implications of Multicalibration"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5684-4585","authenticated-orcid":false,"given":"S\u00edlvia","family":"Casacuberta","sequence":"first","affiliation":[{"name":"University of Oxford, Oxford, United Kingdom"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7177-3738","authenticated-orcid":false,"given":"Cynthia","family":"Dwork","sequence":"additional","affiliation":[{"name":"Harvard University, Cambridge, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4059-4072","authenticated-orcid":false,"given":"Salil","family":"Vadhan","sequence":"additional","affiliation":[{"name":"Harvard University, Cambridge, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,6,11]]},"reference":[{"key":"e_1_3_2_1_1_1","unstructured":"Boaz Barak. 2022. Introduction to Theoretical Computer Science. Creative Commons. https:\/\/files.boazbarak.org\/introtcs\/lnotes_book.pdf."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1093\/jamia\/ocaa283"},{"key":"e_1_3_2_1_3_1","volume-title":"Fairness and machine learning: Limitations and opportunities","author":"Barocas Solon","unstructured":"Solon Barocas, Moritz Hardt, and Arvind Narayanan. 2023. Fairness and machine learning: Limitations and opportunities. MIT Press."},{"key":"e_1_3_2_1_4_1","volume-title":"Conference on Fairness, Accountability and Transparency. PMLR, 77-91","author":"Buolamwini Joy","year":"2018","unstructured":"Joy Buolamwini and Timnit Gebru. 2018. Gender shades: intersectional accuracy disparities in commercial gender classification. In Conference on Fairness, Accountability and Transparency. PMLR, 77-91."},{"key":"e_1_3_2_1_5_1","volume-title":"Finding Simple Models of Complex Objects: From Regularity Lemmas to Algorithmic Fairness. Bachelor's thesis","author":"Puig S\u00edlvia Casacuberta","unstructured":"S\u00edlvia Casacuberta Puig. 2023. Finding Simple Models of Complex Objects: From Regularity Lemmas to Algorithmic Fairness. Bachelor's thesis. Harvard University. https:\/\/nrs.harvard.edu\/URN-3:HUL.INSTREPOS: 37376430."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-78372-7_12"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1089\/big.2016.0047"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-46494-6_4"},{"key":"e_1_3_2_1_9_1","volume-title":"Smith","author":"Dodis Yevgeniy","year":"2008","unstructured":"Yevgeniy Dodis, Rafail Ostrovsky, Leonid Reyzin, and Adam D. Smith. 2008."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/060651380"},{"key":"e_1_3_2_1_11_1","unstructured":"Russell Impagliazzo. 2009. Algorithmic dense model theorems and weak regularity. In Unpublished manuscript. https:\/\/simons-institute.github.io\/pseudora ndomness\/pdfs\/nov09.pdf."},{"key":"e_1_3_2_1_12_1","unstructured":"Russell Impagliazzo. 1995. Hard-core distributions for somewhat hard problems."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1995.492584"},{"key":"e_1_3_2_1_14_1","unstructured":"Russell Impagliazzo. 2008. When do sparse sets have dense models. In Talk at the Pseudorandomness in Mathematics and Computer Science Miniworkshop."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/120877982"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"crossref","unstructured":"Dimitar Jetchev and Krzysztof Pietrzak. 2014. How to fake auxiliary input.","DOI":"10.1007\/978-3-642-54242-8_24"},{"key":"e_1_3_2_1_17_1","first-page":"566","volume-title":"Theory of Cryptography-11th Theory of Cryptography Conference, TCC 2014, San Diego, CA, USA, February 24-26, 2014. Proceedings (Lecture Notes in Computer Science). Yehuda Lindell, (Ed.)","volume":"8349","author":"In","unstructured":"In Theory of Cryptography-11th Theory of Cryptography Conference, TCC 2014, San Diego, CA, USA, February 24-26, 2014. Proceedings (Lecture Notes in Computer Science). Yehuda Lindell, (Ed.) Vol. 8349. Springer, 566-590."},{"key":"e_1_3_2_1_18_1","unstructured":"Michael J. Kearns Seth Neel Aaron Roth and Zhiwei Steven Wu. 2018. Preventing fairness gerrymandering: auditing and learning for subgroup fairness."},{"key":"e_1_3_2_1_19_1","volume-title":"Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsm\u00e4ssan","author":"In","year":"2018","unstructured":"In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsm\u00e4ssan, Stockholm, Sweden, July 10-15, 2018 (Proceedings of Machine Learning Research). Jennifer G. Dy and Andreas Krause, (Eds.) Vol. 80."},{"key":"e_1_3_2_1_20_1","unstructured":"PMLR 2569-2577. http:\/\/proceedings.mlr.press\/v80\/kearns18a.html."},{"key":"e_1_3_2_1_21_1","first-page":"4","article-title":"Universal adaptability: target-independent inference that competes with propensity scoring","volume":"119","author":"Kim Michael P","year":"2022","unstructured":"Michael P Kim, Christoph Kern, Shafi Goldwasser, Frauke Kreuter, and Omer Reingold. 2022. Universal adaptability: target-independent inference that competes with propensity scoring. Proceedings of the National Academy of Sciences, 119, 4.","journal-title":"Proceedings of the National Academy of Sciences"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3306618.3314287"},{"key":"e_1_3_2_1_23_1","unstructured":"Jef Larson Surya Mattu Lauren Kirchner and Julia Angwin. 2016. How we analyzed the compas recidivism algorithm. ProPublica (5 2016 ) 9 1."},{"key":"e_1_3_2_1_24_1","unstructured":"Georgy Noarov Ramya Ramalingam Aaron Roth and Stephan Xie. 2023. Highdimensional prediction for sequential decision making. CoRR abs\/2310.17651."},{"key":"e_1_3_2_1_25_1","unstructured":"arXiv: 2310. 17651."},{"key":"e_1_3_2_1_26_1","volume-title":"Vadhan","author":"Reingold Omer","year":"2008","unstructured":"Omer Reingold, Luca Trevisan, Madhur Tulsiani, and Salil P. Vadhan. 2008."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS"},{"key":"e_1_3_2_1_28_1","volume-title":"Univ. Orsay, Orsay, 1976 ). Colloq.","author":"Szemer\u00e9di Endre","year":"1978","unstructured":"Endre Szemer\u00e9di. 1978. Regular partitions of graphs. In Probl\u00e8mes combinatoires et th\u00e9orie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976 ). Colloq."},{"key":"e_1_3_2_1_29_1","unstructured":"Internat. CNRS. Vol. 260. CNRS Paris 399-401. isbn: 2-222-02070-0."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/s"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2009.41"},{"key":"e_1_3_2_1_32_1","volume-title":"USA","author":"Salil","year":"2013","unstructured":"Salil P. Vadhan and Colin Jia Zheng. 2013. A uniform min-max theorem with applications in cryptography. In Advances in Cryptology-CRYPTO 2013-33rd Annual Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2013."},{"key":"e_1_3_2_1_33_1","volume-title":"Part I (Lecture Notes in Computer Science)","author":"Proceedings","unstructured":"Proceedings, Part I (Lecture Notes in Computer Science). Ran Canetti and Juan A. Garay, (Eds.) Vol. 8042. Springer, 93-110."},{"key":"e_1_3_2_1_34_1","volume-title":"Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012","author":"Salil","year":"2012","unstructured":"Salil P. Vadhan and Colin Jia Zheng. 2012. Characterizing pseudoentropy and simplifying pseudorandom generator constructions. In Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19-22, 2012. Howard J. Karlof and Toniann Pitassi, (Eds.) ACM, 817-836."},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","unstructured":"https:\/\/doi.org\/10.1145\/2213977.2214051. 10.1145\/2213977.2214051","DOI":"10.1145\/2213977.2214051"},{"key":"e_1_3_2_1_36_1","unstructured":"James Vincent. 2018. Amazon reportedly scraps internal ai recruiting tool that was biased against women. The Verge 10."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS"}],"event":{"name":"STOC '24: 56th Annual ACM Symposium on Theory of Computing","location":"Vancouver BC Canada","acronym":"STOC '24","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 56th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3618260.3649748","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3618260.3649748","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:03:52Z","timestamp":1750291432000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3618260.3649748"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,10]]},"references-count":37,"alternative-id":["10.1145\/3618260.3649748","10.1145\/3618260"],"URL":"https:\/\/doi.org\/10.1145\/3618260.3649748","relation":{},"subject":[],"published":{"date-parts":[[2024,6,10]]},"assertion":[{"value":"2024-06-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}