Revision #1 Authors: Timothy Gowers, Emanuele Viola

Accepted on: 8th February 2016 22:05

Downloads: 976

Keywords:

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.

TR15-044 Authors: Timothy Gowers, Emanuele Viola

Publication: 2nd April 2015 16:09

Downloads: 1831

Keywords:

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.