Boosting uniformity in quasirandom groups: fast and simple

Abstract

We study the communication complexity of multiplying $k\times t$ elements from the group $H=\text{SL}(2,q)$ in the number-on-forehead model with $k$ parties. We prove a lower bound of $(t\log H)/c^k$. This is an exponential improvement over previous work, and matches the state-of-the-art in the area. Relatedly, we show that the convolution of $k^c$ independent copies of a 3-uniform distribution over $H^m$ is close to a $k$-uniform distribution. This is again an exponential improvement over previous work which needed $c^k$ copies. The proofs are remarkably simple; the results extend to other quasirandom groups. We also show that for any group $H$, any distribution over $H^m$ whose weight-$k$ Fourier coefficients are small is close to a $k$-uniform distribution. This generalizes previous work in the abelian setting, and the proof is simpler.