Given two symbolic matrices $X$ and $Y$ of dimensions $m\times n$ and $n\times m$, respectively, the *rank principle* states that when $m = n+1$ and $A$ is a scalar matrix of rank $n+1$, the equation $XY = A$ is unsatisfiable. When $m$ is arbitrarily larger than $n$ and $A$ has ... 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 >>>

A branching program is a labeled directed graph that, on each input $x$, induces an $s$-$t$ connectivity instance. Nondeterministic branching programs (NBPs) accept an input if there exists an accepting path, whereas parity branching programs ($\oplus$BPs) accept if the number of accepting paths is odd. Wigderson (Structure in Complexity Theory ... more >>>