Under the auspices of the Computational Complexity Foundation (CCF)

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