Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR21-017 | 19th February 2021 21:59

Mixing in non-quasirandom groups


Authors: Timothy Gowers, Emanuele Viola
Publication: 19th February 2021 21:59
Downloads: 425


We initiate a systematic study of mixing in non-quasirandom groups.
Let $A$ and $B$ be two independent, high-entropy distributions over
a group $G$. We show that the product distribution $AB$ is statistically
close to the distribution $F(AB)$ for several choices of $G$ and
$F$, including:

(1) $G$ is the affine group of $2\times2$ matrices, and $F$ sets
the top-right matrix entry to a uniform value,

(2) $G$ is the lamplighter group, that is the wreath product of $\Z_{2}$
and $\Z_{n}$, and $F$ is multiplication by a certain subgroup,

(3) $G$ is $H^{n}$ where $H$ is non-abelian, and $F$ selects a
uniform coordinate and takes a uniform conjugate of it.

The obtained bounds for (1) and (2) are tight.

This work is motivated by and applied to problems in communication
complexity. We consider the 3-party communication problem of deciding
if the product of three group elements multiplies to the identity.
We prove lower bounds for the groups above, which are tight for the
affine and the lamplighter groups.

ISSN 1433-8092 | Imprint