Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR21-017 | 19th February 2021 21:59

Mixing in non-quasirandom groups

RSS-Feed




TR21-017
Authors: Timothy Gowers, Emanuele Viola
Publication: 19th February 2021 21:59
Downloads: 131
Keywords: 


Abstract:

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