ECCC-Report TR22-091https://eccc.weizmann.ac.il/report/2022/091Comments and Revisions published for TR22-091en-usSat, 02 Jul 2022 13:48:08 +0300
Paper TR22-091
| Quasirandom groups enjoy interleaved mixing |
Emanuele Viola,
Harm Derksen
https://eccc.weizmann.ac.il/report/2022/091Let $G$ be a group such that any non-trivial representation has dimension
at least $d$. Let $X=(X_{1},X_{2},\ldots,X_{t})$ and $Y=(Y_{1},Y_{2},\ldots,Y_{t})$
be distributions over $G^{t}$. Suppose that $X$ is independent from
$Y$. We show that for any $g\in G$ we have
\[
\left|\mathbb{P}[X_{1}Y_{1}X_{2}Y_{2}\cdots X_{t}Y_{t}=g]-1/|G|\right|\le\frac{|G|^{2t-1}}{d^{t-1}}\sqrt{\mathbb{E}_{h\in G^{t}}X(h)^{2}}\sqrt{\mathbb{E}_{h\in G^{t}}Y(h)^{2}}.
\]
Our results generalize, improve, and simplify previous works.
Sat, 02 Jul 2022 13:48:08 +0300https://eccc.weizmann.ac.il/report/2022/091