{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:57:06Z","timestamp":1781031426325,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":69,"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-1910534"],"award-info":[{"award-number":["CCF-1910534"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["CCF-2045128"],"award-info":[{"award-number":["CCF-2045128"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["CCF-2106429"],"award-info":[{"award-number":["CCF-2106429"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["CCF-2211238"],"award-info":[{"award-number":["CCF-2211238"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["CCF-1763970"],"award-info":[{"award-number":["CCF-1763970"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["CCF-2107187"],"award-info":[{"award-number":["CCF-2107187"]}],"id":[{"id":"10.13039\/100000001","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.3800761","type":"proceedings-article","created":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:53:56Z","timestamp":1781027636000},"page":"420-431","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Sparsifying Suprema of Gaussian Processes"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6795-8211","authenticated-orcid":false,"given":"Anindya","family":"De","sequence":"first","affiliation":[{"name":"University of Pennsylvania, Philadelphia, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1825-6122","authenticated-orcid":false,"given":"Shivam","family":"Nadimpalli","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7608-1458","authenticated-orcid":false,"given":"Ryan","family":"O'Donnell","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2407-543X","authenticated-orcid":false,"given":"Rocco A.","family":"Servedio","sequence":"additional","affiliation":[{"name":"Columbia University, New York, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,6,9]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1219092.1219097"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"crossref","unstructured":"S. Artstein-Avidan A. Giannopoulos and V.D. Milman. 2015. Asymptotic Geometric Analysis Part I (Mathematical Surveys and Monographs Vol. 202). American Mathematical Society.","DOI":"10.1090\/surv\/202"},{"key":"e_1_3_2_1_3_1","volume-title":"Asymptotic geometric analysis, Part II. 261","author":"Artstein-Avidan Shiri","unstructured":"Shiri Artstein-Avidan, Apostolos Giannopoulos, and Vitali D Milman. 2021. Asymptotic geometric analysis, Part II. 261, American Mathematical Society."},{"key":"e_1_3_2_1_4_1","volume-title":"New Notions and Constructions of Sparsification for Graphs and Hypergraphs. In 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS","author":"Bansal Nikhil","year":"2019","unstructured":"Nikhil Bansal, Ola Svensson, and Luca Trevisan. 2019. New Notions and Constructions of Sparsification for Graphs and Hypergraphs. In 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019. 910\u2013928."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"crossref","unstructured":"Daniel Bartl and Shahar Mendelson. 2025. Uniform mean estimation via generic chaining. arxiv:2502.15116.","DOI":"10.1016\/j.aim.2026.110918"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2492007.2492029"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237827"},{"key":"e_1_3_2_1_8_1","first-page":"1868","volume-title":"Majorizing Measures for the Optimizer. In 12th Innovations in Theoretical Computer Science Conference (ITCS","author":"Borst Sander","year":"2021","unstructured":"Sander Borst, Daniel Dadush, Neil Olver, and Makrand Sinha. 2021. Majorizing Measures for the Optimizer. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). 73:1\u201373:20. isbn:978-3-95977-177-1 issn:1868-8969"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897558"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-03886-5"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611978322.13"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1214\/14-AOS1235"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-014-0565-9"},{"key":"e_1_3_2_1_14_1","volume-title":"Nagaraja","author":"David Herbert A.","year":"2004","unstructured":"Herbert A. David and Haikady N. Nagaraja. 2004. Order statistics. John Wiley & Sons."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451115"},{"key":"e_1_3_2_1_16_1","volume-title":"12th Innovations in Theoretical Computer Science Conference, ITCS","author":"De Anindya","year":"2021","unstructured":"Anindya De, Shivam Nadimpalli, and Rocco A. Servedio. 2021. Quantitative Correlation Inequalities via Semigroup Interpolation. In 12th Innovations in Theoretical Computer Science Conference, ITCS 2021. 185, 69:1\u201369:20."},{"key":"e_1_3_2_1_17_1","volume-title":"Convex Influences. In 13th Innovations in Theoretical Computer Science Conference, ITCS (LIPIcs","volume":"21","author":"De Anindya","unstructured":"Anindya De, Shivam Nadimpalli, and Rocco A. Servedio. 2022. Convex Influences. In 13th Innovations in Theoretical Computer Science Conference, ITCS (LIPIcs, Vol. 215). 53:1\u201353:21."},{"key":"e_1_3_2_1_18_1","volume-title":"Proceedings of the 65th IEEE Symposium on Foundations of Computer Science (FOCS). To appear","author":"De Anindya","unstructured":"Anindya De, Shivam Nadimpalli, and Rocco A. Servedio. 2024. Gaussian Approximation of Convex Sets by Intersections of Halfspaces. In Proceedings of the 65th IEEE Symposium on Foundations of Computer Science (FOCS). To appear"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3717823.3718183"},{"key":"e_1_3_2_1_20_1","volume-title":"Proceedings of the 65th IEEE Symposium on Foundations of Computer Science (FOCS). To appear","author":"Diakonikolas I.","unstructured":"I. Diakonikolas, D. Kane, V. Kontonis, C. Tzamos, and N. Zarifis. 2024. Agnostically Learning Multi-index Models with Queries. In Proceedings of the 65th IEEE Symposium on Foundations of Computer Science (FOCS). To appear"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2012.175.3.8"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-1236(67)90017-1"},{"key":"e_1_3_2_1_23_1","volume-title":"Approximation and Learning of Submodular Functions Using Low-rank Decision Trees. In COLT 2013 - The 26th Annual Conference on Learning Theory (JMLR Workshop and Conference Proceedings","volume":"740","author":"Feldman Vitaly","year":"2013","unstructured":"Vitaly Feldman, Pravesh Kothari, and Jan Vondr\u00e1k. 2013. Representation, Approximation and Learning of Submodular Functions Using Low-rank Decision Trees. In COLT 2013 - The 26th Annual Conference on Learning Theory (JMLR Workshop and Conference Proceedings, Vol. 30). 711\u2013740."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/140958207"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"crossref","unstructured":"Xavier M. Fernique. 1975. Regularite des trajectoires des fonctions aleatoires gaussiennes. In Ecole d\u2019Et\u00e9 de Probabilit\u00e9s de Saint-Flour IV\u20131974. 1\u201396.","DOI":"10.1007\/BFb0080190"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-013-0068-6"},{"key":"e_1_3_2_1_27_1","first-page":"1986","article-title":"On Milman\u2019s inequality and random subspaces which escape through a mesh in R^n","author":"Gordon Yehoram","year":"1988","unstructured":"Yehoram Gordon. 1988. On Milman\u2019s inequality and random subspaces which escape through a mesh in R^n. In Geometric Aspects of Functional Analysis: Israel Seminar (GAFA) 1986\u201387. 84\u2013106.","journal-title":"Geometric Aspects of Functional Analysis: Israel Seminar (GAFA)"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01291425"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1998.743516"},{"key":"e_1_3_2_1_30_1","volume-title":"Sparsifying Sums of Norms. In 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023. 1953","author":"Jambulapati Arun","year":"2023","unstructured":"Arun Jambulapati, James R. Lee, Yang P. Liu, and Aaron Sidford. 2023. Sparsifying Sums of Norms. In 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023. 1953\u20131962."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585136"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"crossref","unstructured":"William B Johnson Joram Lindenstrauss et al. 1984. Extensions of Lipschitz mappings into a Hilbert space. Contemporary mathematics 26 189-206 (1984) 1.","DOI":"10.1090\/conm\/026\/737400"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451061"},{"key":"e_1_3_2_1_34_1","unstructured":"Sanjeev Khanna Aaron (Louie) Putterman and Madhu Sudan. 2024. Efficient Algorithms and New Characterizations for CSP Sparsification. arXiv:2404.06327. Available at arxiv:2404.06327"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jfa.2004.10.009"},{"key":"e_1_3_2_1_36_1","volume-title":"Proc. 49th IEEE Symposium on Foundations of Computer Science (FOCS). 541\u2013550","author":"Klivans A.","unstructured":"A. Klivans, R. O\u2019Donnell, and R. Servedio. 2008. Learning Geometric Concepts via Gaussian Surface Area. In Proc. 49th IEEE Symposium on Foundations of Computer Science (FOCS). 541\u2013550."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2688073.2688093"},{"key":"e_1_3_2_1_38_1","article-title":"Gaussian Measures of Dilatations of Convex Symmetric Sets","volume":"27","author":"Krzysztof Oleszkiewicz Rafa\u0142 Lata\u0142","year":"1999","unstructured":"Rafa\u0142 Lata\u0142 a and Krzysztof Oleszkiewicz. 1999. Gaussian Measures of Dilatations of Convex Symmetric Sets. The Annals of Probability, 27, 4 (1999), 10, 1922\u20131938.","journal-title":"The Annals of Probability"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"crossref","unstructured":"M. Ledoux and M. Talagrand. 1991. Probability in Banach Spaces. Springer.","DOI":"10.1007\/978-3-642-20212-4"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585165"},{"key":"e_1_3_2_1_41_1","volume-title":"International Symposium on Mathematical Programming.","author":"Lov\u00e1sz L\u00e1szl\u00f3 Mikl\u00f3s","year":"1982","unstructured":"L\u00e1szl\u00f3 Mikl\u00f3s Lov\u00e1sz. 1982. Submodular functions and convexity. In International Symposium on Mathematical Programming."},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3485007"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316323"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01940873"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.24"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1214\/13-AAP997"},{"key":"e_1_3_2_1_47_1","volume-title":"A new proof of A. Dvoretzky\u2019s theorem on cross-sections of convex bodies. Funkcional. Anal. i Prilozen, 5","author":"Milman Vitali D","year":"1971","unstructured":"Vitali D Milman. 1971. A new proof of A. Dvoretzky\u2019s theorem on cross-sections of convex bodies. Funkcional. Anal. i Prilozen, 5 (1971), 28\u201337."},{"key":"e_1_3_2_1_48_1","unstructured":"J. Nelson. 2016. Chaining introduction with some computer science applications. Bulletin of the EATCS."},{"key":"e_1_3_2_1_49_1","unstructured":"Samet Oymak and Babak Hassibi. 2010. New null space results and recovery thresholds for matrix rank minimization. arxiv:1011.6326."},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1093\/imaiai\/iax019"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2012.2207945"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591797"},{"key":"e_1_3_2_1_53_1","unstructured":"Sasha. 2011. Answer to \u201cExpectation of the maximum of gaussian random variables \u201d Mathematics StackExchange. Available https:\/\/math.stackexchange.com\/questions\/89030\/expectation-of-the-maximum-of-gaussian-random-variables"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.159"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374456"},{"key":"e_1_3_2_1_56_1","volume-title":"\u201cAlgorithmic Spectral Graph Theory Boot Camp","author":"Srivastava N.","year":"2014","unstructured":"N. Srivastava. 2014. Graph Sparsification. Series of three lectures given as part of the \u201cAlgorithmic Spectral Graph Theory Boot Camp\u201d of the Fall 2014 \u201cAlgorithmic Spectral Graph Theory\u201d program at the Simons Institute. Videos available at https:\/\/simons.berkeley.edu\/graph-sparsification"},{"key":"e_1_3_2_1_57_1","unstructured":"Mihailo Stojnic. 2009. Various thresholds for \u2113 _1-optimization in compressed sensing. arxiv:0907.3666."},{"key":"e_1_3_2_1_58_1","unstructured":"Mihailo Stojnic. 2013. Regularly random duality."},{"key":"e_1_3_2_1_59_1","first-page":"51","article-title":"Gauss and Cauchy measures and \u03b5 -entropy","volume":"185","author":"Sudakov V.","year":"1969","unstructured":"V. Sudakov. 1969. Gauss and Cauchy measures and \u03b5 -entropy. In Doklady Akademii Nauk. 185, 51\u201353.","journal-title":"Doklady Akademii Nauk."},{"key":"e_1_3_2_1_60_1","volume-title":"Regularity of Gaussian processes. Acta Mathematica, 159, none","author":"Talagrand Michel","year":"1987","unstructured":"Michel Talagrand. 1987. Regularity of Gaussian processes. Acta Mathematica, 159, none (1987), 99 \u2013 149."},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02393307"},{"key":"e_1_3_2_1_62_1","volume-title":"Upper and lower bounds for stochastic processes: decomposition theorems. 60","author":"Talagrand Michel","unstructured":"Michel Talagrand. 2022. Upper and lower bounds for stochastic processes: decomposition theorems. 60, Springer Nature."},{"key":"e_1_3_2_1_63_1","unstructured":"Tomasz Tkocz. 2018. Asymptotic Convex Geometry Lecture Notes. https:\/\/www.math.cmu.edu\/~ttkocz\/teaching\/1819\/asympt-conv-geom-notes.pdf"},{"key":"e_1_3_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-27821-4_37"},{"key":"e_1_3_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.21236\/ADA623999"},{"key":"e_1_3_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.4171\/jems\/815"},{"key":"e_1_3_2_1_67_1","volume-title":"Vempala and Ying Xiao","author":"Santosh","year":"2011","unstructured":"Santosh S. Vempala and Ying Xiao. 2011. Structure from Local Optima: Learning Subspace Juntas via Higher Order PCA. arXiv:1108.3329."},{"key":"e_1_3_2_1_68_1","volume-title":"High-Dimensional Probability: An Introduction with Applications in Data Science. 47","author":"Vershynin Roman","unstructured":"Roman Vershynin. 2018. High-Dimensional Probability: An Introduction with Applications in Data Science. 47, Cambridge University Press."},{"key":"e_1_3_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1017\/9781108627771"}],"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.3800761","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3798129.3800761","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:00:14Z","timestamp":1781028014000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3798129.3800761"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,9]]},"references-count":69,"alternative-id":["10.1145\/3798129.3800761","10.1145\/3798129"],"URL":"https:\/\/doi.org\/10.1145\/3798129.3800761","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"}}]}}