Boosting Uniformity in Quasirandom Groups: Fast and Simple

We study the communication complexity of multiplying$k\times t$elements from the group$H$= 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$LI$, 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.