Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > ITERATED GROUP PRODUCTS, COMMUNICATION COMPLEXITY, MIXING, INTERLEAVED GROUP PRODUCT, SPECIAL LINEAR:
Reports tagged with iterated group products, communication complexity, mixing, interleaved group product, special linear:
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 >>>




ISSN 1433-8092 | Imprint