Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR25-022 | 3rd March 2025 17:26

Boosting uniformity in quasirandom groups: fast and simple

RSS-Feed




TR25-022
Authors: Harm Derksen, Chin Ho Lee, Emanuele Viola
Publication: 3rd March 2025 17:57
Downloads: 56
Keywords: 


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.



ISSN 1433-8092 | Imprint