The Poisson approximation theorem states that when $m$ balls are tossed uniformly and randomly into $n$ bins, the distribution of the bin loads can sometimes be approximated by $n$ independent Poisson random variables of mean $m/n$. We show that when the balls are tossed via a random $\mathbb{F}_2$-linear map, ... more >>>

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 >>>