Showing 2026 · cs.DSShow all
2 papers · 2 filters
cs.DS2026
Optimal Sparsifiers for Minkowski Sums and Sums of Seminorms
Arpon Basu, Joshua Brakensiek, Yeyuan Chen +3
We extend the recent work of Reis and Rothvoss on sparsifying sums of norms to the more general task of sparsifying (Minkowski) sums of centrally symmetric, convex sets. A…
cs.DS2026
Optimal Sparsifiers for Abelian Cayley Graphs
Arpon Basu, Pravesh K. Kothari, Raghu Meka +1
We prove that for every Cayley graph over any finite abelian group , there is a weighted Cayley graph with generators that is a spectral sparsifier f…