{"id":1189070,"date":"2026-10-07T13:55:13","date_gmt":"2026-10-07T20:55:13","guid":{"rendered":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/publication\/optimal-sparsifiers-for-minkowski-sums-and-sums-of-seminorms\/"},"modified":"2026-10-16T16:30:44","modified_gmt":"2026-10-16T23:30:44","slug":"optimal-sparsifiers-for-minkowski-sums-and-sums-of-seminorms","status":"publish","type":"msr-research-item","link":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/publication\/optimal-sparsifiers-for-minkowski-sums-and-sums-of-seminorms\/","title":{"rendered":"Optimal Sparsifiers for Minkowski Sums and Sums of Seminorms"},"content":{"rendered":"\n\n\n

We extend the recent work of Reis and Rothvoss on sparsifying sums of \u2113<\/mi>1<\/mn><\/msub><\/mrow><\/math> norms to the more general task of sparsifying (Minkowski) sums of centrally symmetric, convex sets. As our main result, we prove that for any \u03b5<\/mi>&<\/mo>g<\/mi>t<\/mi>;<\/mo>0<\/mn><\/mrow><\/math> and centrally symmetric, convex sets C_1, ldots, C_msubseteqmathbb{R}^n<\/mtext><\/mrow>C_1, ldots, C_msubseteqmathbb{R}^n<\/annotation><\/semantics><\/math> there is a choice of weights lambda_1, dots , lambda_m in mathbb{R}_{geq 0}<\/mtext><\/mrow>lambda_1, dots , lambda_m in mathbb{R}_{geq 0}<\/annotation><\/semantics><\/math> such that at most O<\/mi>(<\/mo>n<\/mi>\/<\/mo>\u03b5<\/mi>2<\/mn><\/msup>)<\/mo><\/mrow><\/math> of the weights are non-zero, and (1 – varepsilon)cdot Csubseteqsum_{i = 1}^mlambda_icdot C_isubseteq(1 + varepsilon)cdot C,<\/mtext><\/mrow>(1 – varepsilon)cdot Csubseteqsum_{i = 1}^mlambda_icdot C_isubseteq(1 + varepsilon)cdot C,<\/annotation><\/semantics><\/math> where C<\/mi>:<\/mo>=<\/mo>C<\/mi>1<\/mn><\/msub>+<\/mo>\u22ef<\/mo>+<\/mo>C<\/mi>m<\/mi><\/msub><\/mrow><\/math> refers to the Minkowski sums of the sets C<\/mi>1<\/mn><\/msub>,<\/mo>\u2026<\/mo>,<\/mo>C<\/mi>m<\/mi><\/msub><\/mrow><\/math>, and \u03bb<\/mi>\u22c5<\/mo>C<\/mi><\/mrow><\/math> refers to the dilation of the set C<\/mi><\/math>. As immediate applications of this result, we obtain sparsifiers of size O<\/mi>(<\/mo>n<\/mi>\/<\/mo>\u03b5<\/mi>2<\/mn><\/msup>)<\/mo><\/mrow><\/math> for sparsifying sums of seminorms in n<\/mi><\/math>-dimensional space, improving on the O<\/mi>(<\/mo>n<\/mi>log<\/mo>(<\/mo>n<\/mi>\/<\/mo>\u03b5<\/mi>)<\/mo>\u22c5<\/mo>log<\/mo>2.5<\/mn><\/msup>(<\/mo>n<\/mi>)<\/mo><\/mrow><\/mrow>\u03b5<\/mi>2<\/mn><\/msup><\/mrow><\/mrow><\/mfrac>)<\/mo><\/mrow><\/math> size sparsifiers from the work of Jambulapati, Lee, Liu, and Sidford (FOCS 2023). This further yields optimal size hypergraph cut sparsifiers with O<\/mi>(<\/mo>n<\/mi>\/<\/mo>\u03b5<\/mi>2<\/mn><\/msup>)<\/mo><\/mrow><\/math> hyperedges, improving on the O<\/mi>(<\/mo>n<\/mi>log<\/mo>(<\/mo>n<\/mi>)<\/mo>\/<\/mo>\u03b5<\/mi>2<\/mn><\/msup>)<\/mo><\/mrow><\/math> size sparsifiers from the work of Chen, Khanna, and Nagda (FOCS 2020). More generally, this also gives optimal size sparsifiers for sums of symmetric submodular functions.<\/p>\n","protected":false},"excerpt":{"rendered":"

We extend the recent work of Reis and Rothvoss on sparsifying sums of \u21131 norms to the more general task of sparsifying (Minkowski) sums of centrally symmetric, convex sets. As our main result, we prove that for any \u03b5>0 and centrally symmetric, convex sets C_1, ldots, C_msubseteqmathbb{R}^nC_1, ldots, C_msubseteqmathbb{R}^n there is a choice of weights […]<\/p>\n","protected":false},"featured_media":0,"template":"","meta":{"msr-url-field":"","msr-podcast-episode":"","msrModifiedDate":"","msrModifiedDateEnabled":false,"ep_exclude_from_search":false,"_classifai_error":"","msr-author-ordering":[{"type":"text","value":"Arpon Basu","user_id":0},{"type":"text","value":"Joshua Brakensiek","user_id":0},{"type":"text","value":"Yeyuan Chen","user_id":0},{"type":"text","value":"Aaron L. Putterman","user_id":0},{"type":"user_nicename","value":"Victor Reis","user_id":"43536"},{"type":"text","value":"Zihan Zhang","user_id":0}],"msr_publishername":"","msr_publisher_other":"","msr_booktitle":"","msr_chapter":"","msr_edition":"","msr_editors":"","msr_how_published":"arXiv","msr_isbn":"","msr_issue":"","msr_journal":"","msr_number":"","msr_organization":"","msr_pages_string":"","msr_page_range_start":"","msr_page_range_end":"","msr_series":"","msr_volume":"","msr_copyright":"","msr_conference_name":"","msr_doi":"","msr_arxiv_id":"2609.20238","msr_mag_id":"","msr_other_authors":"","msr_other_contributors":"","msr_speaker":"","msr_award":"","msr_affiliation":"","msr_institution":"","msr_host":"","msr_version":"","msr_duration":"","msr_release_tracker_id":"","msr_highlight_type":"","msr_date_display_format":"","msr_main_download_label":"","msr_external_link_label":"","msr_doi_label":"","msr_published_date":"2026-07-27","msr_startdate":"","msr_presentation_date":"","msr_highlight_text":"","msr_notes":"","msr_longbiography":"","msr_publicationurl":"","msr_external_url":"","msr_secondary_video_url":"","msr_conference_url":"","msr_journal_url":"","msr_year":2026,"msr_month":7,"msr_day":27,"msr_microsoftintellectualproperty":false,"msr_pub_id":"1aea8c6ab296704fbcaa5390fb871adeac04e5df","msr_publication_uploader":[{"type":"url","title":"https:\/\/arxiv.org\/abs\/2609.20238","label_id":243109,"id":false,"viewUrl":false}],"msr_related_uploader":[],"msr_original_fields_of_study":[],"msr_s2_paper_id":"1aea8c6ab296704fbcaa5390fb871adeac04e5df","msr_s2_pdf_url":"","msr_citation_count_updated":"","msr_citation_count":0,"msr_influential_citations":0,"msr_reference_count":47,"msr_s2_open_access":false,"msr_s2_author_ids":[],"msr_pub_ids":[{"provider":"s2","id":"1aea8c6ab296704fbcaa5390fb871adeac04e5df"},{"provider":"arxiv","id":"2609.20238"},{"provider":"corpusid","id":"292063519"}],"msr_hide_image_in_river":0,"footnotes":""},"msr-research-highlight":[],"research-area":[13561,13546],"msr-publication-type":[270373],"msr-publisher":[],"msr-publication-cta":[],"msr-focus-area":[],"msr-locale":[268875],"msr-post-option":[],"msr-field-of-study":[246691,246907],"msr-conference":[],"msr-journal":[],"msr-impact-theme":[],"msr-pillar":[],"class_list":["post-1189070","msr-research-item","type-msr-research-item","status-publish","hentry","msr-research-area-algorithms","msr-research-area-computational-sciences-mathematics","msr-locale-en_us","msr-field-of-study-computer-science","msr-field-of-study-mathematics"],"msr_publishername":"","msr_edition":"","msr_affiliation":"","msr_published_date":"2026-07-27","msr_host":"","msr_duration":"","msr_version":"","msr_speaker":"","msr_other_contributors":"","msr_booktitle":"","msr_pages_string":"","msr_chapter":"","msr_isbn":"","msr_journal":"","msr_volume":"","msr_number":"","msr_editors":"","msr_series":"","msr_issue":"","msr_organization":"","msr_how_published":"arXiv","msr_notes":"","msr_highlight_text":"","msr_release_tracker_id":"","msr_original_fields_of_study":"","msr_download_urls":"","msr_external_url":"","msr_secondary_video_url":"","msr_longbiography":"","msr_microsoftintellectualproperty":0,"msr_main_download":"","msr_publicationurl":"","msr_doi":"","msr_publication_uploader":[{"type":"url","title":"https:\/\/arxiv.org\/abs\/2609.20238","label_id":243109,"id":false,"viewUrl":false}],"msr_related_uploader":[],"msr_citation_count":0,"msr_citation_count_updated":"","msr_s2_paper_id":"1aea8c6ab296704fbcaa5390fb871adeac04e5df","msr_influential_citations":0,"msr_reference_count":47,"msr_arxiv_id":"2609.20238","msr_s2_author_ids":[],"msr_s2_open_access":false,"msr_s2_pdf_url":null,"msr_attachments":[],"msr-author-ordering":[{"type":"text","value":"Arpon Basu","user_id":0,"rest_url":false},{"type":"text","value":"Joshua Brakensiek","user_id":0,"rest_url":false},{"type":"text","value":"Yeyuan Chen","user_id":0,"rest_url":false},{"type":"text","value":"Aaron L. Putterman","user_id":0,"rest_url":false},{"type":"user_nicename","value":"Victor Reis","user_id":43536,"rest_url":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/microsoft-research\/v1\/researchers?person=Victor Reis"},{"type":"text","value":"Zihan Zhang","user_id":0,"rest_url":false}],"msr_impact_theme":[],"msr_research_lab":[199565],"msr_event":[],"msr_group":[],"msr_project":[],"publication":[],"video":[],"msr-tool":[],"msr_publication_type":"misc","related_content":[],"_links":{"self":[{"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/1189070","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item"}],"about":[{"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/types\/msr-research-item"}],"version-history":[{"count":4,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/1189070\/revisions"}],"predecessor-version":[{"id":1190255,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/1189070\/revisions\/1190255"}],"wp:attachment":[{"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/media?parent=1189070"}],"wp:term":[{"taxonomy":"msr-research-highlight","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-research-highlight?post=1189070"},{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=1189070"},{"taxonomy":"msr-publication-type","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-publication-type?post=1189070"},{"taxonomy":"msr-publisher","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-publisher?post=1189070"},{"taxonomy":"msr-publication-cta","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-publication-cta?post=1189070"},{"taxonomy":"msr-focus-area","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-focus-area?post=1189070"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=1189070"},{"taxonomy":"msr-post-option","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-post-option?post=1189070"},{"taxonomy":"msr-field-of-study","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-field-of-study?post=1189070"},{"taxonomy":"msr-conference","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-conference?post=1189070"},{"taxonomy":"msr-journal","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-journal?post=1189070"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=1189070"},{"taxonomy":"msr-pillar","embeddable":true,"href":"https:\/\/cm-edgetun.pages.dev\/en-us\/research\/wp-json\/wp\/v2\/msr-pillar?post=1189070"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}