Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > NUMBER-ON-FOREHEAD COMMUNICATION COMPLEXITY:
Reports tagged with number-on-forehead communication complexity:
TR25-022 | 3rd March 2025
Harm Derksen, Chin Ho Lee, Emanuele Viola

Boosting uniformity in quasirandom groups: fast and simple

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




ISSN 1433-8092 | Imprint