ECCC-Report TR21-017https://eccc.weizmann.ac.il/report/2021/017Comments and Revisions published for TR21-017en-usFri, 19 Feb 2021 21:59:56 +0200
Paper TR21-017
| Mixing in non-quasirandom groups |
Timothy Gowers,
Emanuele Viola
https://eccc.weizmann.ac.il/report/2021/017We 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.Fri, 19 Feb 2021 21:59:56 +0200https://eccc.weizmann.ac.il/report/2021/017