ECCC-Report TR16-127https://eccc.weizmann.ac.il/report/2016/127Comments and Revisions published for TR16-127en-usFri, 12 Aug 2016 16:13:46 +0300
Paper TR16-127
| The multiparty communication complexity of interleaved group products |
Timothy Gowers,
Emanuele Viola
https://eccc.weizmann.ac.il/report/2016/127Party $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 to determine which of $e$
and $g$ the interleaved product is equal to, using the
least amount of communication.
We show that for all fixed $k$ and all sufficiently large
$t$ the communication is $\Omega(t \log |G|)$, which is
tight. As an application, we establish the security of
the leakage-resilient circuits studied by Miles and Viola
(STOC 2013) in the ``only computation leaks'' model. Our
main technical contribution is of independent interest.
We show that if $X$ is a probability distribution on
$G^m$ such that any two coordinates are uniform in $G^2$,
then a pointwise product of $s$ independent copies of $X$
is nearly uniform in $G^m$, where $s$ depends on $m$
only.Fri, 12 Aug 2016 16:13:46 +0300https://eccc.weizmann.ac.il/report/2016/127