ECCC-Report TR15-044https://eccc.weizmann.ac.il/report/2015/044Comments and Revisions published for TR15-044en-usMon, 08 Feb 2016 22:05:04 +0200
Revision 1
| The communication complexity of interleaved group products |
Timothy Gowers,
Emanuele Viola
https://eccc.weizmann.ac.il/report/2015/044#revision1Alice 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.Mon, 08 Feb 2016 22:05:04 +0200https://eccc.weizmann.ac.il/report/2015/044#revision1
Paper TR15-044
| The communication complexity of interleaved group products |
Timothy Gowers,
Emanuele Viola
https://eccc.weizmann.ac.il/report/2015/044Alice 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.Thu, 02 Apr 2015 16:09:31 +0300https://eccc.weizmann.ac.il/report/2015/044