{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,3]],"date-time":"2026-04-03T02:00:52Z","timestamp":1775181652811,"version":"3.50.1"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2023,11,30]],"date-time":"2023-11-30T00:00:00Z","timestamp":1701302400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"crossref","award":["RGPIN-2015-03907, RGPIN-2022-03329, RGPIN-2019-04804, and DGECR-2019-00027"],"award-info":[{"award-number":["RGPIN-2015-03907, RGPIN-2022-03329, RGPIN-2019-04804, and DGECR-2019-00027"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Institute for Quantum Computing (IQC) at the University of Waterloo"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2023,12,31]]},"abstract":"<jats:p>\n            The celebrated minimax principle of Yao says that for any Boolean-valued function\n            <jats:italic>f<\/jats:italic>\n            with finite domain, there is a distribution \u03bc over the domain of\n            <jats:italic>f<\/jats:italic>\n            such that computing\n            <jats:italic>f<\/jats:italic>\n            to error \u03b5 against inputs from \u03bc is just as hard as computing\n            <jats:italic>f<\/jats:italic>\n            to error \u03b5 on worst-case inputs. Notably, however, the distribution \u03bc depends on the target error level \u03b5: the hard distribution which is tight for bounded error might be trivial to solve to small bias, and the hard distribution which is tight for a small bias level might be far from tight for bounded error levels.\n          <\/jats:p>\n          <jats:p>In this work, we introduce a new type of minimax theorem which can provide a hard distribution \u03bc that works for all bias levels at once. We show that this works for randomized query complexity, randomized communication complexity, some randomized circuit models, quantum query and communication complexities, approximate polynomial degree, and approximate logrank. We also prove an improved version of Impagliazzo\u2019s hardcore lemma.<\/jats:p>\n          <jats:p>Our proofs rely on two innovations over the classical approach of using Von Neumann\u2019s minimax theorem or linear programming duality. First, we use Sion\u2019s minimax theorem to prove a minimax theorem for ratios of bilinear functions representing the cost and score of algorithms.<\/jats:p>\n          <jats:p>Second, we introduce a new way to analyze low-bias randomized algorithms by viewing them as \u201cforecasting algorithms\u201d evaluated by a certain proper scoring rule. The expected score of the forecasting version of a randomized algorithm appears to be a more fine-grained way of analyzing the bias of the algorithm. We show that such expected scores have many elegant mathematical properties\u2014for example, they can be amplified linearly instead of quadratically. We anticipate forecasting algorithms will find use in future work in which a fine-grained analysis of small-bias algorithms is required.<\/jats:p>","DOI":"10.1145\/3626514","type":"journal-article","created":{"date-parts":[[2023,10,18]],"date-time":"2023-10-18T21:38:31Z","timestamp":1697665111000},"page":"1-58","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["A New Minimax Theorem for Randomized Algorithms"],"prefix":"10.1145","volume":"70","author":[{"ORCID":"https:\/\/orcid.org\/0009-0009-4176-8693","authenticated-orcid":false,"given":"Shalev","family":"Ben-David","sequence":"first","affiliation":[{"name":"University of Waterloo, Canada"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-5824-9034","authenticated-orcid":false,"given":"Eric","family":"Blais","sequence":"additional","affiliation":[{"name":"University of Waterloo, Canada"}]}],"member":"320","published-online":{"date-parts":[[2023,11,30]]},"reference":[{"key":"e_1_3_5_4_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976014.5"},{"key":"e_1_3_5_4_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/42282.214084"},{"key":"e_1_3_5_4_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973068.129"},{"key":"e_1_3_5_4_5_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2020.9"},{"key":"e_1_3_5_4_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215070"},{"key":"e_1_3_5_4_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00031"},{"key":"e_1_3_5_4_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00040"},{"key":"e_1_3_5_4_9_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.CCC.2019.29"},{"key":"e_1_3_5_4_10_1","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/305\/05215"},{"key":"e_1_3_5_4_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/130938517"},{"key":"e_1_3_5_4_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/16m1061400"},{"key":"e_1_3_5_4_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-006-1313-z"},{"key":"e_1_3_5_4_14_1","volume-title":"Loss Functions for Binary Class Probability Estimation and Classification: Structure and Applications","author":"Buja Andreas","year":"2005","unstructured":"Andreas Buja, Werner Stuetzle, and Yi Shen. 2005. Loss Functions for Binary Class Probability Estimation and Classification: Structure and Applications. University of Pennsylvania and University of Washington. https:\/\/pdfs.semanticscholar.org\/d670\/6b6e626c15680688b0774419662f2341caee.pdf"},{"key":"e_1_3_5_4_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/0213028"},{"key":"e_1_3_5_4_16_1","doi-asserted-by":"publisher","DOI":"10.1198\/016214506000001437"},{"key":"e_1_3_5_4_17_1","unstructured":"Surbhi Goel Varun Kanade Adam Klivans and Justin Thaler. 2017. Reliably learning the ReLU in polynomial time. In Proceedings of the 2017 Conference on Learning Theory Satyen Kale and Ohad Shamir (Eds). Proceedings of Machine Learning Research Vol. 65. PMLR 1004\u20131042. arXiv:1611.10258 [cs.LG]"},{"key":"e_1_3_5_4_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1995.492584"},{"key":"e_1_3_5_4_19_1","volume-title":"\u00dcber die Genauigkeit der Ann\u00e4herung stetiger Funktionen durch ganze rationale Funktionen gegebenen Grades und trigonometrische Summen gegebener Ordnung","author":"Jackson Dunham","year":"1911","unstructured":"Dunham Jackson. 1911. \u00dcber die Genauigkeit der Ann\u00e4herung stetiger Funktionen durch ganze rationale Funktionen gegebenen Grades und trigonometrische Summen gegebener Ordnung. Ph. D. Dissertation. Dieterichsche University of Buchdrukerei. https:\/\/gdz.sub.uni-goettingen.de\/id\/PPN30230648X"},{"key":"e_1_3_5_4_20_1","doi-asserted-by":"publisher","DOI":"10.1023\/a:1022949332276"},{"key":"e_1_3_5_4_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2009.25"},{"key":"e_1_3_5_4_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2008.25"},{"key":"e_1_3_5_4_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-69416-0_1"},{"key":"e_1_3_5_4_24_1","doi-asserted-by":"publisher","DOI":"10.1142\/1284"},{"key":"e_1_3_5_4_25_1","unstructured":"Yuri P. Ofman. 1962. On the algorithmic complexity of discrete functions. Computational Complexity 145 1 (1962) 48\u201351."},{"key":"e_1_3_5_4_26_1","doi-asserted-by":"publisher","DOI":"10.1147\/rd.312.0235"},{"key":"e_1_3_5_4_27_1","unstructured":"Mark D. Reid and Robert C. Williamson. 2011. Information divergence and risk for binary experiments. Journal of Machine Learning Research 12 22 (2011) 731\u2013817. http:\/\/jmlr.org\/papers\/v12\/reid11a.html"},{"key":"e_1_3_5_4_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/0221053"},{"key":"e_1_3_5_4_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-003-0175-x"},{"key":"e_1_3_5_4_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/110842661"},{"key":"e_1_3_5_4_31_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2013.v009a018"},{"key":"e_1_3_5_4_32_1","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1958.8.171"},{"key":"e_1_3_5_4_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.850703"},{"key":"e_1_3_5_4_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2009.41"},{"key":"e_1_3_5_4_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00071-1"},{"key":"e_1_3_5_4_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-03927-4"},{"key":"e_1_3_5_4_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/35517"},{"key":"e_1_3_5_4_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1977.24"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3626514","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3626514","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T22:50:15Z","timestamp":1750287015000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3626514"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,11,30]]},"references-count":37,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2023,12,31]]}},"alternative-id":["10.1145\/3626514"],"URL":"https:\/\/doi.org\/10.1145\/3626514","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,11,30]]},"assertion":[{"value":"2020-12-04","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-09-02","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-11-30","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}