{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T16:10:04Z","timestamp":1750695004557,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":94,"publisher":"ACM","funder":[{"name":"National Science Foundation","award":["CCF-2211972"],"award-info":[{"award-number":["CCF-2211972"]}]},{"name":"Simons Investigator","award":[""],"award-info":[{"award-number":[""]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,6,15]]},"DOI":"10.1145\/3717823.3718212","type":"proceedings-article","created":{"date-parts":[[2025,6,15]],"date-time":"2025-06-15T22:24:47Z","timestamp":1750026287000},"page":"1614-1625","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Redundancy Is All You Need"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4149-7298","authenticated-orcid":false,"given":"Joshua","family":"Brakensiek","sequence":"first","affiliation":[{"name":"University of California at Berkeley, Berkeley, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7926-3396","authenticated-orcid":false,"given":"Venkatesan","family":"Guruswami","sequence":"additional","affiliation":[{"name":"University of California at Berkeley, Berkeley, 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.1007\/978-3-642-02930-1_27"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.40"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213556.2213560"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.APPROX"},{"key":"e_1_3_2_1_5_1","unstructured":"Ryan Alweiss Brice Huang and Mark Sellke. 2022. Improved Lower Bound for Frankl\u2019s Union-Closed Sets Conjecture. arXiv preprint arXiv:2211.11731."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2840728.2840753"},{"volume-title":"Advances in Neural Information Processing Systems. 32, Curran Associates","author":"Arora Raman","key":"e_1_3_2_1_7_1","unstructured":"Raman Arora and Jalaj Upadhyay. 2019. On Differentially Private Graph Sparsification and Applications. In Advances in Neural Information Processing Systems. 32, Curran Associates, Inc.."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2837020"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/090772873"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237827"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v34i02.5499"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/2540128.2540198"},{"volume-title":"Non learnability of constraint networks with membership queries. Technical report","author":"Bessiere Christian","key":"e_1_3_2_1_13_1","unstructured":"Christian Bessiere and Fr\u00e9d\u00e9ric Koriche. 2012. Non learnability of constraint networks with membership queries. Technical report, Coconut, Montpellier, France."},{"volume-title":"Extending the Scope of Algebraic Kernelization for Constraint Satisfaction Problems. Master\u2019s thesis","author":"Beukers Stijn","key":"e_1_3_2_1_14_1","unstructured":"Stijn Beukers. 2021. Extending the Scope of Algebraic Kernelization for Constraint Satisfaction Problems. Master\u2019s thesis. Eindhoven University of Technology."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","unstructured":"Abhishek Bhowmick Zeev Dvir and Shachar Lovett. 2013. New Lower Bounds for Matching Vector Codes. March https:\/\/doi.org\/10.48550\/arXiv.1204.1367 arxiv:1204.1367. 10.48550\/arXiv.1204.1367","DOI":"10.48550\/arXiv.1204.1367"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.67"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","unstructured":"Joshua Brakensiek and Venkatesan Guruswami. 2024. Redundancy Is All You Need. Nov. https:\/\/doi.org\/10.48550\/arXiv.2411.03451 arxiv:2411.03451. 10.48550\/arXiv.2411.03451","DOI":"10.48550\/arXiv.2411.03451"},{"key":"e_1_3_2_1_18_1","first-page":"3544","article-title":"Adversarial robustness of streaming algorithms through importance sampling","volume":"34","author":"Braverman Vladimir","year":"2021","unstructured":"Vladimir Braverman, Avinatan Hassidim, Yossi Matias, Mariano Schain, Sandeep Silwal, and Samson Zhou. 2021. Adversarial robustness of streaming algorithms through importance sampling. Advances in Neural Information Processing Systems, 34 (2021), 3544\u20133557.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/19M1242446"},{"key":"e_1_3_2_1_20_1","unstructured":"Stijn Cambie. 2022. Better bounds for the union-closed sets conjecture using the entropy approach. arXiv preprint arXiv:2212.12500."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CP.2022.11"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.158"},{"key":"e_1_3_2_1_23_1","unstructured":"Zachary Chase and Shachar Lovett. 2022. Approximate union closed conjecture. arXiv preprint arXiv:2211.11689."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-019-00660-y"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s40324-021-00282-x"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00064"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ITCS.2024.33"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00015"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993674"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNSE.2014.2380315"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2629620"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/100804322"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536422"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02759942"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2005.03.010"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1046186"},{"volume-title":"Extremal set systems. Handbook of combinatorics","author":"Frankl P\u00e9ter","key":"e_1_3_2_1_37_1","unstructured":"P\u00e9ter Frankl. 1995. Extremal set systems. Handbook of combinatorics, Vol. 1, 2, 1293\u20131329."},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218213002000769"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","unstructured":"Justin Gilmer. 2022. A Constant Lower Bound for the Union-Closed Sets Conjecture. Nov. https:\/\/doi.org\/10.48550\/arXiv.2211.09055 arxiv:2211.09055. 10.48550\/arXiv.2211.09055","DOI":"10.48550\/arXiv.2211.09055"},{"key":"e_1_3_2_1_40_1","unstructured":"Parikshit Gopalan. 2009. A note on Efremenko\u2019s locally decodable codes. In Electronic Colloquium on Computational Complexity (ECCC). 69."},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2012.2208937"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","unstructured":"Yuxin Guo Deyu Bo Cheng Yang Zhiyuan Lu Zhongjian Zhang Jixi Liu Yufei Peng and Chuan Shi. 2024. Data-Centric Graph Learning: A Survey. Jan. https:\/\/doi.org\/10.48550\/arXiv.2310.04987 arxiv:2310.04987. 10.48550\/arXiv.2310.04987","DOI":"10.48550\/arXiv.2310.04987"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.93.063107"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1137\/060668092"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1006\/JCSS.2001.1774"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-42071-0_8"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3349618"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2002.03443"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/990308.990313"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451061"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1137\/141002281"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.5555\/313559.313605"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139004114.004"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.5555\/2634074.2634090"},{"key":"e_1_3_2_1_55_1","unstructured":"Yotam Kenneth and Robert Krauthgamer. 2023. Cut sparsification and succinct representation of submodular hypergraphs. arXiv preprint arXiv:2307.09110."},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977912.185"},{"key":"e_1_3_2_1_57_1","unstructured":"Sanjeev Khanna Aaron L. Putterman and Madhu Sudan. 2024. Efficient Algorithms and New Characterizations for CSP Sparsification. April arxiv:2404.06327."},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2407.03934"},{"key":"e_1_3_2_1_59_1","volume-title":"Graph generated union-closed families of sets. arXiv preprint math\/9409215, 229","author":"Knill Emanuel","year":"1994","unstructured":"Emanuel Knill. 1994. Graph generated union-closed families of sets. arXiv preprint math\/9409215, 229 (1994)."},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/2688073.2688093"},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1137\/110845914"},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-66158-2_11"},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/3389411"},{"key":"e_1_3_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICTAI.2010.16"},{"key":"e_1_3_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.52"},{"key":"e_1_3_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1061850"},{"key":"e_1_3_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/331524.331526"},{"key":"e_1_3_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1145\/3437963.3441734"},{"key":"e_1_3_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1145\/2627692.2627694"},{"volume-title":"Probability and Computing: Randomized Algorithms and Probabilistic Analysis","author":"Mitzenmacher Michael","key":"e_1_3_2_1_70_1","unstructured":"Michael Mitzenmacher and Eli Upfal. 2005. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, USA. isbn:978-0-521-83540-4"},{"volume-title":"Randomized Algorithms","author":"Motwani Rajeev","key":"e_1_3_2_1_71_1","unstructured":"Rajeev Motwani and Prabhakar Raghavan. 1995. Randomized Algorithms. Cambridge University Press."},{"key":"e_1_3_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICTAI.2008.83"},{"key":"e_1_3_2_1_73_1","doi-asserted-by":"publisher","unstructured":"Luke Pebody. 2022. Extension of a Method of Gilmer. Nov. https:\/\/doi.org\/10.48550\/arXiv.2211.13139 arxiv:2211.13139. 10.48550\/arXiv.2211.13139","DOI":"10.48550\/arXiv.2211.13139"},{"key":"e_1_3_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977912.187"},{"key":"e_1_3_2_1_75_1","unstructured":"Akbar Rafiey. 2024. Decomposable Submodular Maximization in Federated Setting. arXiv preprint arXiv:2402.00138."},{"key":"e_1_3_2_1_76_1","unstructured":"Prasad Raghavendra. 2007. A note on Yekhanin\u2019s locally decodable codes. In Electronic Colloquium on Computational Complexity (ECCC) TR07-016."},{"key":"e_1_3_2_1_77_1","volume-title":"Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely","author":"Ruzsa I. Z.","year":"1976","unstructured":"I. Z. Ruzsa and E. Szemer\u00e9di. 1978. Triple systems with no six points carrying three triangles. In Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. II (Colloq. Math. Soc. J\u00e1nos Bolyai, Vol. 18). North-Holland, Amsterdam-New York, 939\u2013945."},{"key":"e_1_3_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989399"},{"key":"e_1_3_2_1_79_1","doi-asserted-by":"publisher","unstructured":"Will Sawin. 2023. An Improved Lower Bound for the Union-Closed Set Conjecture. June https:\/\/doi.org\/10.48550\/arXiv.2211.11504 arxiv:2211.11504. 10.48550\/arXiv.2211.11504","DOI":"10.48550\/arXiv.2211.11504"},{"key":"e_1_3_2_1_80_1","unstructured":"Gregory Schwartzman. 2024. Mini-batch Submodular Maximization. arXiv preprint arXiv:2401.12478."},{"key":"e_1_3_2_1_81_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02018585"},{"key":"e_1_3_2_1_82_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007372"},{"key":"e_1_3_2_1_83_1","doi-asserted-by":"publisher","DOI":"10.1137\/08074489X"},{"key":"e_1_3_2_1_84_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.paerosci.2022.100823"},{"key":"e_1_3_2_1_85_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10601-022-09340-1"},{"volume-title":"Minimum","author":"Todd Michael J.","key":"e_1_3_2_1_86_1","unstructured":"Michael J. Todd. 2016. Minimum volume ellipsoids - theory and algorithms (MOS-SIAM Series on Optimization, Vol. 23). SIAM. isbn:978-1-611-97437-9"},{"key":"e_1_3_2_1_87_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10701-018-0166-z"},{"key":"e_1_3_2_1_88_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000054"},{"volume-title":"Two Studies of Constraints in High Dimensions: Entropy Inequalities and the Randomized Symmetric Binary Perceptron. Master\u2019s thesis","author":"Wakhare Tanay","key":"e_1_3_2_1_89_1","unstructured":"Tanay Wakhare. 2024. Two Studies of Constraints in High Dimensions: Entropy Inequalities and the Randomized Symmetric Binary Perceptron. Master\u2019s thesis. Massachusetts Institute of Technology."},{"key":"e_1_3_2_1_90_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(98)00208-8"},{"key":"e_1_3_2_1_91_1","doi-asserted-by":"publisher","DOI":"10.1145\/1326554.1326555"},{"key":"e_1_3_2_1_92_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000030"},{"key":"e_1_3_2_1_93_1","doi-asserted-by":"publisher","DOI":"10.3390\/e25050767"},{"key":"e_1_3_2_1_94_1","doi-asserted-by":"publisher","unstructured":"Shichang Zhang Atefeh Sohrabizadeh Cheng Wan Zijie Huang Ziniu Hu Yewen Wang Yingyan Lin Jason Cong and Yizhou Sun. 2023. A Survey on Graph Neural Network Acceleration: Algorithms Systems and Customized Hardware. June https:\/\/doi.org\/10.48550\/arXiv.2306.14052 arxiv:2306.14052. 10.48550\/arXiv.2306.14052","DOI":"10.48550\/arXiv.2306.14052"}],"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.3718212","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T15:43:54Z","timestamp":1750693434000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3717823.3718212"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,15]]},"references-count":94,"alternative-id":["10.1145\/3717823.3718212","10.1145\/3717823"],"URL":"https:\/\/doi.org\/10.1145\/3717823.3718212","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"}}]}}