{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:56:59Z","timestamp":1781031419876,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":101,"publisher":"ACM","license":[{"start":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T00:00:00Z","timestamp":1780963200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["CCF-2239265"],"award-info":[{"award-number":["CCF-2239265"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"Amazon","doi-asserted-by":"publisher","award":["Research Award"],"award-info":[{"award-number":["Research Award"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"Google","doi-asserted-by":"publisher","award":["Research Scholar Award, PhD Fellowship"],"award-info":[{"award-number":["Research Scholar Award, PhD Fellowship"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"Simons Foundation","doi-asserted-by":"publisher","award":["Investigator Award 689988"],"award-info":[{"award-number":["Investigator Award 689988"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004399","name":"Okawa Foundation for Information and Telecommunications","doi-asserted-by":"publisher","award":["Award"],"award-info":[{"award-number":["Award"]}],"id":[{"id":"10.13039\/501100004399","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2026,6,9]]},"DOI":"10.1145\/3798129.3800739","type":"proceedings-article","created":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:53:56Z","timestamp":1781027636000},"page":"186-197","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["A Unified Approach to Memory-Sample Tradeoffs for Detecting Planted Structures"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8069-6655","authenticated-orcid":false,"given":"Sumegha","family":"Garg","sequence":"first","affiliation":[{"name":"Rutgers University, New Brunswick, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6173-1366","authenticated-orcid":false,"given":"Jabari","family":"Hastings","sequence":"additional","affiliation":[{"name":"Stanford University, Stanford, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3424-691X","authenticated-orcid":false,"given":"Chirag","family":"Pabbaraju","sequence":"additional","affiliation":[{"name":"Stanford University, Stanford, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-1280-5623","authenticated-orcid":false,"given":"Vatsal","family":"Sharan","sequence":"additional","affiliation":[{"name":"University of Southern California, Los Angeles, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,6,9]]},"reference":[{"key":"e_1_3_2_1_1_1","first-page":"1","article-title":"Community detection and stochastic block models: recent developments","volume":"18","author":"Abbe Emmanuel","year":"2018","unstructured":"Emmanuel Abbe. 2018. Community detection and stochastic block models: recent developments. Journal of Machine Learning Research, 18, 177 (2018), 1\u201386. https:\/\/jmlr.org\/papers\/v18\/16-480.html","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.neucom.2017.04.070"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250863"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199810\/12)13:3\/4<457::AID-RSA14>3.0.CO;2-W"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-011-0459-x"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","unstructured":"Alexandr Andoni Andrew McGregor Krzysztof Onak and Rina Panigrahy. 2008. Better bounds for frequency moments in random-order streams. arXiv preprint arXiv:0808.2222 https:\/\/doi.org\/10.48550\/arXiv.0808.2222 10.48550\/arXiv.0808.2222","DOI":"10.48550\/arXiv.0808.2222"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806715"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.1506.01900"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1002\/cpa.22083"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1999.1062"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3623800.3623808"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.14778\/2140436.2140442"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.1204.3514"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.11.006"},{"key":"e_1_3_2_1_15_1","first-page":"577","article-title":"Non-asymptotic minimax rates of testing in signal detection","volume":"8","author":"YANNICK","year":"2002","unstructured":"YANNICK BARAUD. 2002. Non-asymptotic minimax rates of testing in signal detection. Bernoulli, 8, 5 (2002), 577\u2013606. https:\/\/projecteuclid.org\/journals\/bernoulli\/volume-8\/issue-5\/Non-asymptotic-minimax-rates-of-testing-in-signal-detection\/bj\/1078435219.full","journal-title":"Bernoulli"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2006.07971"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.1304.0828"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897582"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649672"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00038"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-017-0277-5"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2005.08099"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2009.06107"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2206.04743"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585184"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374470"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331599"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.1402.1267"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1214\/15-AOS1432"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.1611.09744"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-96151-4_9"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2019.45"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ESA.2016.32"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.1902.03498"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.1803.01420"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-023-09603-0"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1214\/009053604000000265"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0807471105"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1214\/14-STS506"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00058"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.1902.00582"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.53"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2204.07526"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1998.743518"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(200003)16:2<195::AID-RSA5>3.0.CO;2-A"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3046674"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2506.01855"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.1506.06737"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.1405.1665"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188962"},{"key":"e_1_3_2_1_51_1","unstructured":"Sudipto Guha and Andrew McGregor. 2007. Space-efficient sampling. In Artificial Intelligence and Statistics. 171\u2013178. https:\/\/proceedings.mlr.press\/v2\/guha07a.html"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1214\/09-AOS764"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","unstructured":"Magn\u00fas M Halld\u00f3rsson Xiaoming Sun Mario Szegedy and Chengu Wang. 2012. Streaming and communication complexity of clique approximation. In International Colloquium on Automata Languages and Programming. 449\u2013460. https:\/\/doi.org\/10.1007\/978-3-642-31594-7_38 10.1007\/978-3-642-31594-7_38","DOI":"10.1007\/978-3-642-31594-7_38"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.72"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","unstructured":"Yuri I Ingster. 1996. On some problems of hypothesis testing leading to infinitely divisible distributions. https:\/\/doi.org\/10.20347\/WIAS.PREPRINT.215 10.20347\/WIAS.PREPRINT.215","DOI":"10.20347\/WIAS.PREPRINT.215"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","unstructured":"Yu. I. Ingster and I. A. Suslina. 2003. Nonparametric goodness-of-fit testing under Gaussian models (Lecture Notes in Statistics Vol. 169). Springer-Verlag New York. https:\/\/doi.org\/10.1007\/978-0-387-21580-8 10.1007\/978-0-387-21580-8","DOI":"10.1007\/978-0-387-21580-8"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1214\/0009053607000000244"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.1602.06929"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1002\/RSA.3240030402"},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","unstructured":"Iain M Johnstone and Arthur Yu Lu. 2009. Sparse principal components analysis. arXiv preprint arXiv:0901.4392 https:\/\/doi.org\/10.48550\/arXiv.0901.4392 10.48550\/arXiv.0901.4392","DOI":"10.48550\/arXiv.0901.4392"},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/3294052.3319706"},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.112"},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.55"},{"key":"e_1_3_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/100216.100262"},{"key":"e_1_3_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1093\/biostatistics\/kxs030"},{"key":"e_1_3_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-32512-0_20"},{"key":"e_1_3_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(94)00103-K"},{"key":"e_1_3_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2022.84"},{"key":"e_1_3_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2402.07240"},{"key":"e_1_3_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1145\/3653298"},{"key":"e_1_3_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2015.7282733"},{"key":"e_1_3_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1088\/1742-5468\/aa7284"},{"key":"e_1_3_2_1_73_1","volume-title":"Proceedings of Thirty Eighth Conference on Learning Theory. PMLR. https:\/\/proceedings.mlr.press\/v291\/li25d.html","author":"Li Qian","year":"2025","unstructured":"Qian Li, Shuo Wang, and Jiapeng Zhang. 2025. Multi-Pass Memory Lower Bounds for Learning Problems. In Proceedings of Thirty Eighth Conference on Learning Theory. PMLR. https:\/\/proceedings.mlr.press\/v291\/li25d.html"},{"key":"e_1_3_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS57990.2023.00056"},{"key":"e_1_3_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.3390\/app13106353"},{"key":"e_1_3_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.1507.06370"},{"key":"e_1_3_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.1214\/14-AOS1300"},{"key":"e_1_3_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.0908.0050"},{"key":"e_1_3_2_1_79_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939783"},{"key":"e_1_3_2_1_80_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2021.34"},{"key":"e_1_3_2_1_81_1","doi-asserted-by":"publisher","unstructured":"Jay Mardia. 2021. Logspace Reducibility From Secret Leakage Planted Clique. arXiv preprint arXiv:2107.11886 https:\/\/doi.org\/10.48550\/arXiv.2107.11886 10.48550\/arXiv.2107.11886","DOI":"10.48550\/arXiv.2107.11886"},{"key":"e_1_3_2_1_82_1","doi-asserted-by":"publisher","DOI":"10.1145\/3689208"},{"key":"e_1_3_2_1_83_1","doi-asserted-by":"publisher","DOI":"10.1145\/2627692.2627694"},{"key":"e_1_3_2_1_84_1","doi-asserted-by":"publisher","DOI":"10.5555\/874063.875554"},{"key":"e_1_3_2_1_85_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.1307.0032"},{"key":"e_1_3_2_1_86_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2016.2549542"},{"key":"e_1_3_2_1_87_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2107.01335"},{"key":"e_1_3_2_1_88_1","doi-asserted-by":"publisher","DOI":"10.1145\/3186563"},{"key":"e_1_3_2_1_89_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.1311.3494"},{"key":"e_1_3_2_1_90_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.1804.03065"},{"key":"e_1_3_2_1_91_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316403"},{"key":"e_1_3_2_1_92_1","volume-title":"Conference on Learning Theory. 1564\u20131587","author":"Steinhardt Jacob","year":"2015","unstructured":"Jacob Steinhardt and John Duchi. 2015. Minimax rates for memory-bounded sparse linear regression. In Conference on Learning Theory. 1564\u20131587. https:\/\/proceedings.mlr.press\/v40\/Steinhardt15.html"},{"key":"e_1_3_2_1_93_1","volume-title":"Conference on Learning Theory. 1490\u20131516","author":"Steinhardt Jacob","year":"2016","unstructured":"Jacob Steinhardt, Gregory Valiant, and Stefan Wager. 2016. Memory, communication, and statistical queries. In Conference on Learning Theory. 1490\u20131516. https:\/\/proceedings.mlr.press\/v49\/steinhardt16.pdf"},{"key":"e_1_3_2_1_94_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2025.89"},{"key":"e_1_3_2_1_95_1","volume-title":"Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence -","volume":"1516","author":"Tan Swee Chuan","year":"2011","unstructured":"Swee Chuan Tan, Kai Ming Ting, and Tony Fei Liu. 2011. Fast anomaly detection for streaming data. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence - Volume Volume Two (IJCAI\u201911). AAAI Press, 1511\u20131516. https:\/\/www.ijcai.org\/Proceedings\/11\/Papers\/254.pdf"},{"key":"e_1_3_2_1_96_1","doi-asserted-by":"publisher","DOI":"10.1109\/ITW.2016.7606821"},{"key":"e_1_3_2_1_97_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2102.01583"},{"key":"e_1_3_2_1_98_1","volume-title":"International Conference on Machine Learning. 494\u2013503","author":"Yang Wenzhuo","year":"2015","unstructured":"Wenzhuo Yang and Huan Xu. 2015. Streaming sparse principal component analysis. In International Conference on Machine Learning. 494\u2013503. https:\/\/proceedings.mlr.press\/v37\/yangd15.html"},{"key":"e_1_3_2_1_99_1","volume-title":"Information-theoretic lower bounds for distributed statistical estimation with communication constraints. Advances in Neural Information Processing Systems, 26","author":"Zhang Yuchen","year":"2013","unstructured":"Yuchen Zhang, John Duchi, Michael I Jordan, and Martin J Wainwright. 2013. Information-theoretic lower bounds for distributed statistical estimation with communication constraints. Advances in Neural Information Processing Systems, 26 (2013), https:\/\/proceedings.neurips.cc\/paper_files\/paper\/2013\/file\/d6ef5f7fa914c19931a55bb262ec879c-Paper.pdf"},{"key":"e_1_3_2_1_100_1","doi-asserted-by":"publisher","DOI":"10.1198\/106186006X113430"},{"key":"e_1_3_2_1_101_1","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2018.2846588"}],"event":{"name":"STOC '26: 58th Annual ACM Symposium on Theory of Computing","location":"Salt Lake City UT USA","acronym":"STOC '26","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 58th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3798129.3800739","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3798129.3800739","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:58:48Z","timestamp":1781027928000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3798129.3800739"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,9]]},"references-count":101,"alternative-id":["10.1145\/3798129.3800739","10.1145\/3798129"],"URL":"https:\/\/doi.org\/10.1145\/3798129.3800739","relation":{},"subject":[],"published":{"date-parts":[[2026,6,9]]},"assertion":[{"value":"2026-06-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}