Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR15-044 | 8th February 2016 22:05

The communication complexity of interleaved group products

RSS-Feed




Revision #1
Authors: Timothy Gowers, Emanuele Viola
Accepted on: 8th February 2016 22:05
Downloads: 245
Keywords: 


Abstract:

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 which is the case.

We show that for every $t \ge 2$ communication $\Omega(t
\log |G|)$ is required, even for randomized protocols
achieving only an advantage $\eps = |G|^{-\Omega(t)}$
over random guessing. This bound is tight, improves on
the previous lower bound of $\Omega(t)$, and answers a
question of Miles and Viola (STOC 2013). An extension of
our result to 8-party number-on-forehead protocols would
suffice for their intended application to
leakage-resilient circuits.

Our communication bound is equivalent to the assertion
that if $(a_1,\ldots,a_t)$ and $(b_1,\ldots,b_t)$ are
sampled uniformly from large subsets $A$ and $B$ of $G^t$
then their interleaved product is nearly uniform over $G
= \text{SL}(2,q)$. This extends results by Gowers
(Combinatorics, Probability {\&} Computing, 2008) and by
Babai, Nikolov, and Pyber (SODA 2008) corresponding to
the independent case where $A$ and $B$ are product sets.
We also obtain an alternative proof of their result that
the product of three independent, high-entropy elements
of $G$ is nearly uniform. Unlike the previous proofs,
ours does not rely on representation theory.


Paper:

TR15-044 | 2nd April 2015 16:08

The communication complexity of interleaved group products





TR15-044
Authors: Timothy Gowers, Emanuele Viola
Publication: 2nd April 2015 16:09
Downloads: 1018
Keywords: 


Abstract:

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 which is the case.

We show that for every $t \ge 2$ communication $\Omega(t
\log |G|)$ is required, even for randomized protocols
achieving only an advantage $\eps = |G|^{-\Omega(t)}$
over random guessing. This bound is tight, improves on
the previous lower bound of $\Omega(t)$, and answers a
question of Miles and Viola (STOC 2013). An extension of
our result to 8-party number-on-forehead protocols would
suffice for their intended application to
leakage-resilient circuits.

Our communication bound is equivalent to the assertion
that if $(a_1,\ldots,a_t)$ and $(b_1,\ldots,b_t)$ are
sampled uniformly from large subsets $A$ and $B$ of $G^t$
then their interleaved product is nearly uniform over $G
= \text{SL}(2,q)$. This extends results by Gowers
(Combinatorics, Probability {\&} Computing, 2008) and by
Babai, Nikolov, and Pyber (SODA 2008) corresponding to
the independent case where $A$ and $B$ are product sets.
We also obtain an alternative proof of their result that
the product of three independent, high-entropy elements
of $G$ is nearly uniform. Unlike the previous proofs,
ours does not rely on representation theory.



ISSN 1433-8092 | Imprint