Repository logo
 

INTERLEAVED GROUP PRODUCTS

Accepted version
Peer-reviewed

Loading...
Thumbnail Image

Type

Article

Change log

Authors

Gowers, WT 
Viola, Emanuele 

Abstract

Let G be the special linear group SL(2,q). We show that if (a1,…,at) and (b1,…,bt) are sampled uniformly from large subsets A and B of Gt then their interleaved product a1b1a2b2⋯atbt is nearly uniform over G. This extends a result of the first author, which corresponds to the independent case where A and B are product sets. We obtain a number of other results. For example, we show that if X is a probability distribution on Gm such that any two coordinates are uniform in G2, then a pointwise product of s independent copies of X is nearly uniform in Gm, where s depends on m only. Extensions to other groups are also discussed. We obtain closely related results in communication complexity, which is the setting where some of these questions were first asked by Miles and Viola. For example, suppose party Ai of k parties A1,…,Ak receives on its forehead a t-tuple (ai1,…,ait) of elements from G. The parties are promised that the interleaved product a11ak1a12ak2a1takt is equal either to the identity e or to some other fixed element gG, and their goal is to determine which of the two the product is equal to. We show that for all fixed k and all sufficiently large t the communication is Ω(tlog⁡|G|), which is tight. Even for k=2 the previous best lower bound was Ω(t). As an application, we establish the security of the leakage-resilient circuits studied by Miles and Viola in the "only computation leaks" model.

Description

Keywords

iterated group products, communication complexity, mixing, interleaved group product, special linear group, conjugacy class, representation theory, quasi-random group

Journal Title

SIAM JOURNAL ON COMPUTING

Conference Name

Journal ISSN

0097-5397
1095-7111

Volume Title

48

Publisher

Society for Industrial & Applied Mathematics (SIAM)
Sponsorship
Royal Society (RP90066)
Royal Society (RP/EA/180019)