Sparsity is a basis-dependent notion: a polynomial with many monomials may become sparse after an invertible affine change of variables. We study polynomial identity testing (PIT) and lower bounds for sparse polynomials under arbitrary invertible affine changes of coordinates, that is, for affine orbits of sparse polynomials. For PIT, the ... more >>>

This paper studies when list-decodability guarantees for error-correcting codes of good distance can go beyond the classical Johnson radius and gives a corresponding efficient list-decoding algorithm for Reed-Solomon codes up to this new radius. The Johnson bound shows that any error-correcting code with distance $\delta$ is automatically list-decodable with small ... more >>>

A recent manuscript of OpenAI proves that the exponent of matrix multiplication satisfies $\omega\le9/4$. We give an elementary, self-contained proof of this bound. We follow the ideas of the original manuscript, but implement them differently to obtain explicit algorithms. Specifically, for every $\varepsilon>0$, we give a matrix multiplication algorithm with ... more >>>