Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR26-132 | 4th August 2026 20:03

Optimal Sparsifiers for Minkowski Sums and Sums of Seminorms

RSS-Feed




TR26-132
Authors: Arpon Basu, Joshua Brakensiek, Yeyuan Chen, Aaron (Louie) Putterman, Victor Reis, Zihan Zhang
Publication: 4th August 2026 20:08
Downloads: 15
Keywords: 


Abstract:

We extend the recent work of Reis and Rothvoss on sparsifying sums of $\ell_1$ norms to the more general task of sparsifying (Minkowski) sums of centrally symmetric, convex sets. As our main result, we prove that for any $\varepsilon > 0$ and centrally symmetric, convex sets $C_1, \ldots, C_m\subseteq\mathbb R^n$ there is a choice of weights $\lambda_1, \dots , \lambda_m \in \mathbb R_{\geq 0}$ such that at most $O(n / \varepsilon^2)$ of the weights are non-zero, and
\[(1 - \varepsilon)\cdot C\subseteq\sum_{i = 1}^m\lambda_i\cdot C_i\subseteq(1 + \varepsilon)\cdot C,\]
where $C:= C_1 + \cdots + C_m$ refers to the Minkowski sums of the sets $C_1, \ldots, C_m$, and $\lambda\cdot C$ refers to the dilation of the set $C$.

As immediate applications of this result, we obtain sparsifiers of size $O(n / \varepsilon^2)$ for sparsifying sums of seminorms in $n$-dimensional space, improving on the $O\left ( \frac{n \log(n/\varepsilon) \cdot \log^{2.5}(n)}{\varepsilon^2} \right )$ size sparsifiers from the work of Jambulapati, Lee, Liu, and Sidford (FOCS 2023). This further yields optimal size hypergraph cut sparsifiers with $O(n / \varepsilon^2)$ hyperedges, improving on the $O(n \log(n) / \varepsilon^2)$ 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.



ISSN 1433-8092 | Imprint