{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T16:10:05Z","timestamp":1750695005631,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":39,"publisher":"ACM","funder":[{"name":"National Science Foundation","award":["1934876, 2008305, 2152413"],"award-info":[{"award-number":["1934876, 2008305, 2152413"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,6,15]]},"DOI":"10.1145\/3717823.3718205","type":"proceedings-article","created":{"date-parts":[[2025,6,15]],"date-time":"2025-06-15T22:24:47Z","timestamp":1750026287000},"page":"407-416","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Efficient Algorithms and New Characterizations for CSP Sparsification"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0000-2601-1689","authenticated-orcid":false,"given":"Sanjeev","family":"Khanna","sequence":"first","affiliation":[{"name":"University of Pennsylvania, Philadelphia, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9737-2406","authenticated-orcid":false,"given":"Aaron","family":"Putterman","sequence":"additional","affiliation":[{"name":"Harvard University, Cambridge, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3718-6489","authenticated-orcid":false,"given":"Madhu","family":"Sudan","sequence":"additional","affiliation":[{"name":"Harvard University, Cambridge, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-9260(95)00008-4"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3015144"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01263424"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536451"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237827"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Joshua Brakensiek and Venkatesan Guruswami. 2024. Redundancy Is All You Need. arXiv preprint arXiv:2411.03451.","DOI":"10.1145\/3717823.3718212"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/19M1242446"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00015"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2002.806118"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/090772721"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1046186"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611978322.43"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.71"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/3104322.3104373"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFB0045075"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.CH12"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2305.09049"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585136"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/313559.313605"},{"key":"e_1_3_2_1_20_1","volume-title":"Cut Sparsification and Succinct Representation of Submodular Hypergraphs. CoRR, abs\/2307.09110","author":"Kenneth Yotam","year":"2023","unstructured":"Yotam Kenneth and Robert Krauthgamer. 2023. Cut Sparsification and Succinct Representation of Submodular Hypergraphs. CoRR, abs\/2307.09110 (2023), arXiv:2307.09110. arxiv:2307.09110"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977912.185"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2688073.2688093"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1002\/NET.3230030306"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585165"},{"key":"e_1_3_2_1_25_1","volume-title":"Inhomogeneous Hypergraph Clustering with Applications. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017","author":"Li Pan","year":"2017","unstructured":"Pan Li and Olgica Milenkovic. 2017. Inhomogeneous Hypergraph Clustering with Applications. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett (Eds.). 2308\u20132318. https:\/\/proceedings.neurips.cc\/paper\/2017\/hash\/a50abba8132a77191791390c3eb19fe7-Abstract.html"},{"key":"e_1_3_2_1_26_1","volume-title":"Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsm\u00e4ssan","author":"Li Pan","year":"2018","unstructured":"Pan Li and Olgica Milenkovic. 2018. Submodular Hypergraphs: p-Laplacians, Cheeger Inequalities and Spectral Clustering. In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsm\u00e4ssan, Stockholm, Sweden, July 10-15, 2018, Jennifer G. Dy and Andreas Krause (Eds.) (Proceedings of Machine Learning Research, Vol. 80). PMLR, 3020\u20133029. http:\/\/proceedings.mlr.press\/v80\/li18e.html"},{"key":"e_1_3_2_1_27_1","volume-title":"The 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, Proceedings of the Conference","author":"Lin Hui","year":"2011","unstructured":"Hui Lin and Jeff A. Bilmes. 2011. A Class of Submodular Functions for Document Summarization. In The 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, Proceedings of the Conference, 19-24 June, 2011, Portland, Oregon, USA, Dekang Lin, Yuji Matsumoto, and Rada Mihalcea (Eds.). The Association for Computer Linguistics, 510\u2013520. https:\/\/aclanthology.org\/P11-1052\/"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3442381.3449887"},{"key":"e_1_3_2_1_29_1","unstructured":"Daniele Miccancio. 2014. Point Lattices. 1\u201313. https:\/\/cseweb.ucsd.edu\/classes\/sp14\/cse206A-a\/lec1.pdf Reading material for CSE 206A: Lattice Algorithms and Applications."},{"volume-title":"A book of abstract algebra (dover ed. ed.)","author":"Pinter Charles C.","key":"e_1_3_2_1_30_1","unstructured":"Charles C. Pinter. 2010. A book of abstract algebra (dover ed. ed.). Dover Publications, Mineola, N.Y.. isbn:978-0486474175 lccn:09026228"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/08074489X"},{"key":"e_1_3_2_1_32_1","volume-title":"Learning Mixtures of Submodular Functions for Image Collection Summarization. In Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014","author":"Tschiatschek Sebastian","year":"2014","unstructured":"Sebastian Tschiatschek, Rishabh K. Iyer, Haochen Wei, and Jeff A. Bilmes. 2014. Learning Mixtures of Submodular Functions for Image Collection Summarization. In Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014, December 8-13 2014, Montreal, Quebec, Canada, Zoubin Ghahramani, Max Welling, Corinna Cortes, Neil D. Lawrence, and Kilian Q. Weinberger (Eds.). 1413\u20131421. https:\/\/proceedings.neurips.cc\/paper\/2014\/hash\/a8e864d04c95572d1aece099af852d0a-Abstract.html"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.641542"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3394486.3403222"},{"key":"e_1_3_2_1_35_1","volume-title":"Austin R. Benson, and Jon M. Kleinberg","author":"Veldt Nate","year":"2021","unstructured":"Nate Veldt, Austin R. Benson, and Jon M. Kleinberg. 2021. Approximate Decomposable Submodular Function Minimization for Cardinality-Based Components. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, Marc\u2019Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan (Eds.). 3744\u20133756. https:\/\/proceedings.neurips.cc\/paper\/2021\/hash\/1e8a19426224ca89e83cef47f1e7f53b-Abstract.html"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/20M1321048"},{"key":"e_1_3_2_1_37_1","volume-title":"Talukdar","author":"Yadati Naganand","year":"2019","unstructured":"Naganand Yadati, Madhav Nimishakavi, Prateek Yadav, Vikram Nitin, Anand Louis, and Partha P. Talukdar. 2019. HyperGCN: A New Method For Training Graph Convolutional Networks on Hypergraphs. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d\u2019Alch\u00e9-Buc, Emily B. Fox, and Roman Garnett (Eds.). 1509\u20131520. https:\/\/proceedings.neurips.cc\/paper\/2019\/hash\/1efa39bcaec6f3900149160693694536-Abstract.html"},{"key":"e_1_3_2_1_38_1","volume-title":"Proceedings of the Twentieth Annual Conference on Neural Information Processing Systems","author":"Zhou Dengyong","year":"2006","unstructured":"Dengyong Zhou, Jiayuan Huang, and Bernhard Sch\u00f6lkopf. 2006. Learning with Hypergraphs: Clustering, Classification, and Embedding. In Advances in Neural Information Processing Systems 19, Proceedings of the Twentieth Annual Conference on Neural Information Processing Systems, Vancouver, British Columbia, Canada, December 4-7, 2006, Bernhard Sch\u00f6lkopf, John C. Platt, and Thomas Hofmann (Eds.). MIT Press, 1601\u20131608. https:\/\/proceedings.neurips.cc\/paper\/2006\/hash\/dff8e9c2ac33381546d96deea9922999-Abstract.html"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/IEEECONF56349.2022.10052065"}],"event":{"name":"STOC '25: 57th Annual ACM Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Prague Czechia","acronym":"STOC '25"},"container-title":["Proceedings of the 57th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3717823.3718205","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T15:43:37Z","timestamp":1750693417000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3717823.3718205"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,15]]},"references-count":39,"alternative-id":["10.1145\/3717823.3718205","10.1145\/3717823"],"URL":"https:\/\/doi.org\/10.1145\/3717823.3718205","relation":{},"subject":[],"published":{"date-parts":[[2025,6,15]]},"assertion":[{"value":"2025-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}