{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,29]],"date-time":"2026-06-29T12:46:50Z","timestamp":1782737210142,"version":"3.54.5"},"reference-count":44,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2026,6,30]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>We consider the question of Gaussian mean testing, a fundamental task in high-dimensional distribution testing and signal processing, subject to adversarial corruptions of the samples. We focus on the relative power of different adversaries and show that, in contrast to the common wisdom in robust statistics, there exists a strict separation between adaptive adversaries (strong contamination) and oblivious ones (weak contamination) for this task. Specifically, we resolve both the information-theoretic and computational landscapes for robust mean testing. In the exponential-time setting, we establish the tight sample complexity of testing [Formula: see text] against [Formula: see text], where [Formula: see text], with an [Formula: see text]-fraction of oblivious adversarial corruptions, to be [Formula: see text], while the complexity against adaptive adversarial corruptions is [Formula: see text], which is strictly worse for a large range of vanishing [Formula: see text]. To the best of our knowledge, ours is the first separation in sample complexity between the strong and weak contamination models. In the polynomial-time setting, we close a gap in the literature by providing a polynomial-time algorithm against adaptive adversaries achieving the above sample complexity [Formula: see text], and a low-degree lower bound (which complements an existing reduction from planted clique) suggesting that all efficient algorithms require this many samples, even in the oblivious-adversary setting.<\/jats:p>","DOI":"10.1137\/24m1636435","type":"journal-article","created":{"date-parts":[[2026,4,15]],"date-time":"2026-04-15T08:00:37Z","timestamp":1776240037000},"page":"FOCS23-192-FOCS23-267","source":"Crossref","is-referenced-by-count":0,"title":["The Full Landscape of Robust Mean Testing: Sharp Separations between Oblivious and Adaptive Contamination"],"prefix":"10.1137","volume":"55","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7153-5211","authenticated-orcid":true,"given":"Cl\u00e9ment","family":"Canonne","sequence":"first","affiliation":[{"name":"School of Computer Science, University of Sydney, Sydney, NSW, Australia."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Samuel B.","family":"Hopkins","sequence":"additional","affiliation":[{"name":"Department of Electrical Engineering and Computer Science, MIT, Cambridge, MA 02139 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jerry","family":"Li","sequence":"additional","affiliation":[{"name":"Microsoft Research, Redmond, WA 98052 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Allen","family":"Liu","sequence":"additional","affiliation":[{"name":"Department of Electrical Engineering and Computer Science, MIT, Cambridge, MA 02139 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shyam","family":"Narayanan","sequence":"additional","affiliation":[{"name":"Department of Electrical Engineering and Computer Science, MIT, Cambridge, MA 02139 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2026,4,15]]},"reference":[{"key":"ref1","unstructured":"J. Acharya, C. L. Canonne, and H. Tyagi, Distributed signal detection under communication constraints, in Proceedings of Thirty-Third Conference on Learning Theory, Proc. Mach. Learn. Res. 125, PMLR, 2020, pp. 41\u201363, http:\/\/proceedings.mlr.press\/v125\/acharya20b.html."},{"key":"ref2","first-page":"14106","volume-title":"Advances in Neural Information Processing Systems","volume":"33","author":"Asi H.","year":"2020"},{"key":"ref3","first-page":"1121","author":"Asi H.","year":"2023","journal-title":"ICML"},{"key":"ref4","doi-asserted-by":"crossref","unstructured":"M.F. Balcan and N. Haghtalab, Noise in classification, in Beyond the Worst-Case Analysis of Algorithms, 2020, pp. 361\u2013381, https:\/\/dblp.org\/rec\/books\/cu\/20\/BalcanH20.html?view=bibtex.","DOI":"10.1017\/9781108637435.022"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1137\/17M1138236"},{"key":"ref6","first-page":"577","volume":"8","author":"Baraud Y.","year":"2002","journal-title":"Bernoulli"},{"key":"ref7","unstructured":"G. Blanc, J. Lange, A. Malik, and L.Y. Tan, On the power of adaptivity in statistical adversaries, in Conference on Learning Theory, PMLR, 2022, pp. 5030\u20135061."},{"key":"ref8","unstructured":"M. Brennan and G. Bresler, Reducibility and statistical-computational gaps from secret leakage, in Conference on Learning Theory, PMLR, 2020, pp. 648\u2013847."},{"key":"ref9","unstructured":"M. S. Brennan, G. Bresler, S. B. Hopkins, J. Li, and T. Schramm, Statistical Query Algorithms and Low-Degree Tests Are Almost Equivalent, in Proceedings of Machine Learning Research, Conference on Learning Theory, PMLR, 2021, http:\/\/proceedings.mlr.press\/v134\/brennan21a.html."},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00403-0"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.21"},{"key":"ref12","first-page":"10099","volume-title":"NeurIPS","author":"Canonne C. L.","year":"2020"},{"key":"ref13","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1016\/S1874-5849(01)80010-3","volume-title":"in Handbook of the geometry of Banach spaces","volume":"1","author":"Davidson K. R.","year":"2001"},{"key":"ref14","first-page":"10862","volume":"34","author":"Deng S.","year":"2021","journal-title":"Adv. Neural Inform. Process. Syst."},{"key":"ref15","volume":"32","author":"Diakonikolas I.","year":"2019","journal-title":"Adv. Neural Inform. Process. Syst."},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1137\/17M1126680"},{"key":"ref17","doi-asserted-by":"crossref","unstructured":"I. Diakonikolas, G. Kamath, D. M. Kane, J. Li, A. Moitra, and A. Stewart, Robustly learning a Gaussian:\u00a0Getting optimal error, efficiently, in Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 2018, pp. 2683\u20132702, https:\/\/doi.org\/10.1137\/1.9781611975031.171.","DOI":"10.1137\/1.9781611975031.171"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.52202\/068431-0262"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1017\/9781108943161"},{"key":"ref20","series-title":"COLT, Proc. Mach. Learn. Res. 134","first-page":"1511","author":"Diakonikolas I.","year":"2021"},{"key":"ref21","doi-asserted-by":"crossref","unstructured":"I. Diakonikolas, D. M. Kane, and A. Pensia, Gaussian mean testing made simple, in Symposium on Simplicity in Algorithms (SOSA), SIAM, 2023, pp. 348\u2013352, https:\/\/doi.org\/10.1137\/1.9781611977585.ch31.","DOI":"10.1137\/1.9781611977585.ch31"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.16"},{"key":"ref23","doi-asserted-by":"crossref","unstructured":"I. Diakonikolas, D. M. Kane, and A. Stewart, Learning geometric concepts with nasty noise, in Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018, pp. 1061\u20131073.","DOI":"10.1145\/3188745.3188754"},{"key":"ref24","volume":"32","author":"Dong Y.","year":"2019","journal-title":"Adv. Neural Inform. Process. Syst."},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1137\/1135098"},{"key":"ref26","doi-asserted-by":"crossref","unstructured":"A. J. George and C. L. Canonne, Robust testing in high-dimensional sparse models, in Proceedings of the 36th Conference on Neural Information Processing Systems (NeurIPS 2022), Curran Associates, 2022, pp. 16469\u201316480.","DOI":"10.52202\/068431-1198"},{"key":"ref27","doi-asserted-by":"crossref","unstructured":"K. Georgiev and S. B. Hopkins, Privacy induces robustness: Information-computation gaps and sparse mean estimation, in NIPS\u201922: Proceedings of the 36th International Conference on Neural Information Processing Systems (NeurIPS 2022), Curran Associates,\u00a02022, pp. 6829\u20136842.","DOI":"10.52202\/068431-0495"},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2022.3162397"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.3150\/15-BEJ800"},{"key":"ref30","unstructured":"S. Hopkins, Statistical Inference and the Sum of Squares Method, Ph.D. thesis, Cornell University, 2018."},{"key":"ref31","doi-asserted-by":"crossref","unstructured":"S. B. Hopkins, G. Kamath, M. Majid, and S. Narayanan, Robustness Implies Privacy in Statistical Estimation, in Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC, 2023, pp. 497\u2013506, https:\/\/doi.org\/10.1145\/3564246.3585115.","DOI":"10.1145\/3564246.3585115"},{"key":"ref32","doi-asserted-by":"crossref","unstructured":"S. B. Hopkins and D. Steurer, Efficient Bayesian estimation from few samples: Community detection and related problems, in 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, 2017, pp. 379\u2013390.","DOI":"10.1109\/FOCS.2017.42"},{"key":"ref33","volume-title":"Robust Statistics","author":"Huber P. J.","year":"2011"},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-21580-8"},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.1145\/293347.293351"},{"key":"ref36","doi-asserted-by":"publisher","DOI":"10.1109\/SPW50608.2020.00028"},{"key":"ref37","first-page":"1","volume-title":"Mathematical Analysis, Its Applications and Computation: ISAAC 2019","author":"Kunisky D.","year":"2019"},{"key":"ref38","unstructured":"S. Narayanan, Private high-dimensional hypothesis testing, in Proceedings of 35th Conference on Learning Theory (COLT), Proc. Mach. Learn. Res. 178, PMLR, 2022, pp. 3979\u20134027."},{"key":"ref39","unstructured":"R. Nasser and S. Tiegel, Optimal SQ lower bounds for learning halfspaces with Massart noise, in Proceedings of 35th Conference on Conference on Learning Theory (COLT), Proc. Mach. Learn. Res. 178, PMLR, 2022, pp. 1047\u20131074."},{"key":"ref40","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176988477"},{"key":"ref41","unstructured":"M. Skala, Hypergeometric Tail Inequalities:\u00a0Ending the Insanity, CoRR preprint, abs\/1311.5939, (2013)."},{"key":"ref42","doi-asserted-by":"publisher","DOI":"10.1016\/j.jmva.2006.11.002"},{"key":"ref43","doi-asserted-by":"publisher","DOI":"10.1214\/23-AOS2269"},{"key":"ref44","author":"Wilcox R. R.","year":"1997","journal-title":"Introduction to Robust Estimation and Hypothesis Testing"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","deposited":{"date-parts":[[2026,6,29]],"date-time":"2026-06-29T12:15:20Z","timestamp":1782735320000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/24M1636435"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,4,15]]},"references-count":44,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2026,6,30]]}},"alternative-id":["10.1137\/24M1636435"],"URL":"https:\/\/doi.org\/10.1137\/24m1636435","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,4,15]]}}}