All reports by Author Timothy Gowers:

__
TR21-017
| 19th February 2021
__

Timothy Gowers, Emanuele Viola#### Mixing in non-quasirandom groups

__
TR16-127
| 12th August 2016
__

Timothy Gowers, Emanuele Viola#### The multiparty communication complexity of interleaved group products

__
TR15-044
| 2nd April 2015
__

Timothy Gowers, Emanuele Viola#### The communication complexity of interleaved group products

Revisions: 1

Timothy Gowers, Emanuele Viola

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 ... more >>>

Timothy Gowers, Emanuele Viola

Party $A_i$ of $k$ parties $A_1,\dots,A_k$ receives on

its forehead a $t$-tuple $(a_{i1},\dots,a_{it})$ of

elements from the group $G=\text{SL}(2,q)$. The parties

are promised that the interleaved product $a_{11}\dots

a_{k1}a_{12}\dots a_{k2}\dots a_{1t}\dots a_{kt}$ is

equal either to the identity $e$ or to some other fixed

element $g\in G$. Their goal is ...
more >>>

Timothy Gowers, Emanuele Viola

Alice receives a tuple $(a_1,\ldots,a_t)$ of $t$ elements

from the group $G = \text{SL}(2,q)$. Bob similarly

receives a tuple $(b_1,\ldots,b_t)$. They are promised

that the interleaved product $\prod_{i \le t} a_i b_i$

equals to either $g$ and $h$, for two fixed elements $g,h

\in G$. Their task is to decide ...
more >>>