In coding theory, list recoverability is a fundamental concept which robustly captures how ``spread-out'' codewords are in a code.
More formally, given a code $C \subseteq \Sigma^n$ and input lists $S_1, \hdots, S_n \subseteq \Sigma$ of size at most $\ell$, list recoverability requires that there are at most $L$ codewords ... more >>>

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$ ... more >>>

We give a deterministic white-box algorithm to estimate the expectation of a read-once branching program of length $n$ and width $w$ in space
$$\tilde{O}\left(\log n+\sqrt{\log n}\cdot\log w\right).$$
In particular, we obtain an almost optimal space $\tilde{O}(\log n)$ derandomization of programs up to width $w=2^{\sqrt{\log n}}$.
Previously, ... more >>>