The communication complexity of interleaved group products
W. T. Gowers, Emanuele Viola · 2015
Alice receives a tuple (a1,...,at) of t elements from the group G = SL(2,q). Bob similarly receives a tuple of t elements (b1,...,bt). They are promised that the interleaved product prodi ≤ t ai bi equals to either g and h, for two fixed elements g,h ∈ G. Their task is to decide which is the case.