2024/09/11 by Harm Derksen, Derksen, Harm, Chin Ho Lee +3 · 1 citation
Mathematics · #Combinatorics (math.CO) #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Spectral Theory in Mathematical Physics
paper · pdf · doi:10.48550/arxiv.2409.06932
openalex publication_date 2024/09/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the communication complexity of multiplying k× t elements from the group H=SL(2,q) in the number-on-forehead model with k parties. We prove a lower bound of (tlog H)/ck. 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 kc independent copies of a 3-uniform distribution over Hm is close to a k-uniform distribution. This is again an exponential improvement over previous work which needed ck copies. The proofs are remarkably simple; the results extend to other quasirandom groups. We also show that for any group H, any distribution over Hm 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.