  Under the auspices of the Computational Complexity Foundation (CCF)     REPORTS > AUTHORS > TIMOTHY GOWERS:
All reports by Author Timothy Gowers:

TR21-017 | 19th February 2021
Timothy Gowers, Emanuele Viola

#### Mixing in non-quasirandom groups

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

TR16-127 | 12th August 2016
Timothy Gowers, Emanuele Viola

#### The multiparty communication complexity of interleaved group products

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

TR15-044 | 2nd April 2015
Timothy Gowers, Emanuele Viola

#### The communication complexity of interleaved group products

Revisions: 1

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

ISSN 1433-8092 | Imprint