{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,13]],"date-time":"2025-10-13T15:35:36Z","timestamp":1760369736070,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":48,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,6,15]],"date-time":"2021-06-15T00:00:00Z","timestamp":1623715200000},"content-version":"vor","delay-in-days":0,"URL":"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":[[2021,6,15]]},"DOI":"10.1145\/3406325.3451135","type":"proceedings-article","created":{"date-parts":[[2021,6,16]],"date-time":"2021-06-16T01:26:13Z","timestamp":1623806773000},"page":"116-122","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Statistical query complexity of manifold estimation"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4516-3009","authenticated-orcid":false,"given":"Eddie","family":"Aamari","sequence":"first","affiliation":[{"name":"LPSM, France \/ Sorbonne University, France \/ University of Paris, France \/ CNRS, France"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4311-9071","authenticated-orcid":false,"given":"Alexander","family":"Knop","sequence":"additional","affiliation":[{"name":"University of California at San Diego, USA"}]}],"member":"320","published-online":{"date-parts":[[2021,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1214\/19-EJS1551"},{"key":"e_1_3_2_1_2_1","volume-title":"November","author":"Aamari Eddie","year":"2020","unstructured":"Eddie Aamari and Alexander Knop. Statistical Query Complexity of Manifold Estimation. arXiv e-prints, page arXiv:2011.04259, November 2020."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-017-9962-z"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1214\/18-AOS1685"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/2567709.2567719"},{"key":"e_1_3_2_1_6_1","volume-title":"Quantum statistical query learning. CoRR, abs\/2002.08240","author":"Arunachalam Srinivasan","year":"2020","unstructured":"Srinivasan Arunachalam, Alex B. Grilo, and Henry Yuen. Quantum statistical query learning. CoRR, abs\/2002.08240, 2020."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1569"},{"key":"e_1_3_2_1_8_1","volume-title":"January","author":"Berenfeld Cl\u00e9ment","year":"2020","unstructured":"Cl\u00e9ment Berenfeld, John Harvey, Marc Hoffmann, and Krishnan Shankar. Estimating the reach of a manifold via its convexity defect function. arXiv e-prints, page arXiv:2001.08006, January 2020."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195147"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-013-9557-2"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/180139.181176"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1030741073"},{"key":"e_1_3_2_1_13_1","first-page":"511","volume-title":"Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015","author":"Dachman-Soled Dana","year":"2015","unstructured":"Dana Dachman-Soled, Vitaly Feldman, Li-Yang Tan, Andrew Wan, and Karl Wimmer. Approximate resilience, monotonicity, and the complexity of agnostic learning. In Piotr Indyk, editor, Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 498\u2013511. SIAM, 2015."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.16"},{"key":"e_1_3_2_1_15_1","volume-title":"Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017","author":"Ding Bolin","year":"2017","unstructured":"Bolin Ding, Janardhan Kulkarni, and Sergey Yekhanin. Collecting telemetry data privately. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 4-9 December 2017, Long Beach, CA, USA, pages 3571\u20133580, 2017."},{"key":"e_1_3_2_1_16_1","volume-title":"Minimax adaptive estimation in manifold inference","author":"Divol Vincent","year":"2020","unstructured":"Vincent Divol. Minimax adaptive estimation in manifold inference, 2020."},{"key":"e_1_3_2_1_17_1","volume-title":"February","author":"Divol Vincent","year":"2021","unstructured":"Vincent Divol. Reconstructing measures on manifolds: an optimal transport approach. arXiv e-prints, page arXiv:2102.07595, February 2021."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-007-0095-7"},{"key":"e_1_3_2_1_19_1","series-title":"Lecture Notes in Comput","first-page":"284","volume-title":"Theory of cryptography","author":"Dwork Cynthia","unstructured":"Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography, volume 3876 of Lecture Notes in Comput. Sci., pages 265\u2013284. Springer, Berlin, 2006."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2660267.2660348"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/773153.773174"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACSSC.2008.5074571"},{"key":"e_1_3_2_1_23_1","first-page":"830","volume-title":"Proceedings of Machine Learning Research","volume":"65","author":"Feldman Vitaly","year":"2017","unstructured":"Vitaly Feldman. A general characterization of the statistical query complexity. In Proceedings of Machine Learning Research, volume 65, pages 785\u2013830, Amsterdam, Netherlands, 2017."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3046674"},{"key":"e_1_3_2_1_25_1","first-page":"1277","volume-title":"Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Feldman Vitaly","unstructured":"Vitaly Feldman, Crist\u00f3bal Guzm\u00e1n, and Santosh Vempala. Statistical query algorithms for mean vector estimation and stochastic convex optimization. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1265\u20131277. SIAM, Philadelphia, PA, 2017."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1078471"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1214\/12-AOS994"},{"key":"e_1_3_2_1_28_1","first-page":"1263","article-title":"Minimax manifold estimation","volume":"13","author":"Genovese Christopher R.","year":"2012","unstructured":"Christopher R. Genovese, Marco Perone-Pacifico, Isabella Verdinelli, and Larry Wasserman. Minimax manifold estimation. J. Mach. Learn. Res., 13:1263\u20131291, 2012.","journal-title":"J. Mach. Learn. Res."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-84858-7"},{"key":"e_1_3_2_1_30_1","volume-title":"Census bureau adopts cutting edge privacy protections for 2020 census","author":"Ron Jarmin DR.","year":"2019","unstructured":"DR. Ron Jarmin. Census bureau adopts cutting edge privacy protections for 2020 census, 2019. available at https:\/\/www.census.gov\/newsroom\/blogs\/random-samplings\/2019\/02\/census_bureau_adopts.html."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3187009.3177733"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/090756090"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/293347.293351"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1214\/15-EJS1039"},{"key":"e_1_3_2_1_35_1","volume-title":"Lee and Michel Verleysen. Nonlinear dimensionality reduction. Information Science and Statistics","author":"John","year":"2007","unstructured":"John A. Lee and Michel Verleysen. Nonlinear dimensionality reduction. Information Science and Statistics. Springer, New York, 2007."},{"key":"e_1_3_2_1_36_1","volume-title":"June","author":"Puchkin Nikita","year":"2019","unstructured":"Nikita Puchkin and Vladimir Spokoiny. Structure-adaptive manifold estimation. arXiv e-prints, page arXiv:1906.05014, June 2019."},{"key":"e_1_3_2_1_37_1","volume-title":"Shraddha Sahay, and Parvez Ahammad. Linkedin's audience engagements API: A privacy preserving data analytics system at scale. CoRR, abs\/2002.05839","author":"Rogers Ryan","year":"2020","unstructured":"Ryan Rogers, Subbu Subramaniam, Sean Peng, David Durfee, Seunghyun Lee, Santosh Kumar Kancha, Shraddha Sahay, and Parvez Ahammad. Linkedin's audience engagements API: A privacy preserving data analytics system at scale. CoRR, abs\/2002.05839, 2020."},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.290.5500.2323"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-008-0242-4"},{"key":"e_1_3_2_1_40_1","series-title":"JMLR Workshop and Conference Proceedings","first-page":"1516","volume-title":"Proceedings of the 29th Conference on Learning Theory, COLT","author":"Steinhardt Jacob","year":"2016","unstructured":"Jacob Steinhardt, Gregory Valiant, and Stefan Wager. Memory, communication, and statistical queries. In Vitaly Feldman, Alexander Rakhlin, and Ohad Shamir, editors, Proceedings of the 29th Conference on Learning Theory, COLT 2016, New York, USA, June 23-26, 2016, volume 49 of JMLR Workshop and Conference Proceedings, pages 1490\u20131516. JMLR.org, 2016."},{"key":"e_1_3_2_1_41_1","volume-title":"Learning with privacy at scale","author":"Team Differential Privacy","year":"2017","unstructured":"Differential Privacy Team. Learning with privacy at scale, 2017. available at https:\/\/machinelearning.apple.com\/research\/learning-with-privacy-at-scale."},{"key":"e_1_3_2_1_42_1","first-page":"688","volume-title":"Denver","author":"Tenenbaum Joshua B.","year":"1997","unstructured":"Joshua B. Tenenbaum. Mapping a manifold of perceptual observations. In Michael I. Jordan, Michael J. Kearns, and Sara A. Solla, editors, Advances in Neural Information Processing Systems 10, [NIPS Conference, Denver, Colorado, USA, 1997], pages 682\u2013688. The MIT Press, 1997."},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1968.1972"},{"key":"e_1_3_2_1_44_1","first-page":"326","volume-title":"Proceedings of the Third Annual Workshop on Computational Learning Theory, COLT 1990","author":"Verbeurgt Karsten A.","year":"1990","unstructured":"Karsten A. Verbeurgt. Learning DNF under the uniform distribution in quasi-polynomial time. In Mark A. Fulk and John Case, editors, Proceedings of the Third Annual Workshop on Computational Learning Theory, COLT 1990, University of Rochester, Rochester, NY, USA, August 6-8, 1990, pages 314\u2013326. Morgan Kaufmann, 1990."},{"key":"e_1_3_2_1_45_1","first-page":"290","volume-title":"Proceedings of the International Congress of Mathematicians\u2013-Seoul","author":"Wainwright Martin J.","year":"2014","unstructured":"Martin J. Wainwright. Constrained forms of statistical minimax: computation, communication, and privacy. In Proceedings of the International Congress of Mathematicians\u2013-Seoul 2014. Vol. IV, pages 273\u2013290. Kyung Moon Sa, Seoul, 2014."},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1965.10480775"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1146\/annurev-statistics-031017-100045"},{"key":"e_1_3_2_1_48_1","first-page":"435","volume-title":"Festschrift for Lucien Le Cam","author":"Assouad Bin Yu.","unstructured":"Bin Yu. Assouad, fano, and le cam. In Festschrift for Lucien Le Cam, pages 423\u2013435. Springer, 1997."}],"event":{"name":"STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Virtual Italy","acronym":"STOC '21"},"container-title":["Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451135","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451135","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:24:53Z","timestamp":1750195493000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451135"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,15]]},"references-count":48,"alternative-id":["10.1145\/3406325.3451135","10.1145\/3406325"],"URL":"https:\/\/doi.org\/10.1145\/3406325.3451135","relation":{},"subject":[],"published":{"date-parts":[[2021,6,15]]},"assertion":[{"value":"2021-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}