In a $k$-XOR game $\Psi$ over $\mathbb{F}_p$, a verifier samples challenges $(x_1,\ldots,x_k)\sim\mu$ where $\mu$ is a distribution over $\Sigma_1\times\ldots\times \Sigma_k$, sends $x_i$ to player $i$ and receives an answer $f_i(x_i)\in\mathbb{F}_p$, and accepts if and only if $f_1(x_1)+\ldots+f_k(x_k)=t(x_1,\ldots,x_k)$, where $t\colon \Sigma_1\times\ldots\times \Sigma_k\to\mathbb{F}_p$ is a fixed map. We show that if $\Psi$ ... more >>>

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