Spencer's 1985 ``six standard deviations suffice''theorem shows that every $A \in [-1,1]^{n \times n}$ has a sign vector $x \in \{-1,1\}^n$ with $\|Ax\|_\infty \le 6\sqrt{n}$. We show the upper bound $\sqrt{3\operatorname{arsinh}(10)}\sqrt{n}+4<2.9992 \sqrt{n} + 4$ by directly rounding the minimizer of a potential func...
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...
Arpon Basu, Joshua Brakensiek, Ye-Yuan Chen et al.· 0 citations
We prove weighted matroid equitability. Let $M=(E,\mathcal{I})$ be a matroid whose ground set can be partitioned into $k$ bases, and assign a nonnegative weight to every element. Then $E$ has a partition into $k$ bases such that the weights of any two bases differ by at most the largest element weight. We present two p...
Kristóf Bérczi, Si-Yue Liu, Victor Reis et al.· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
