License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2022.80
URN: urn:nbn:de:0030-drops-156761
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/15676/
Go to the corresponding LIPIcs Volume Portal

Gowers, W. T. ; Viola, Emanuele

Mixing in Non-Quasirandom Groups

pdf-format:
LIPIcs-ITCS-2022-80.pdf (0.5 MB)

Abstract

We initiate a systematic study of mixing in non-quasirandom groups. Let A and B be two independent, high-entropy distributions over a group G. We show that the product distribution AB is statistically close to the distribution F(AB) for several choices of G and F, including:
1) G is the affine group of 2x2 matrices, and F sets the top-right matrix entry to a uniform value,
2) G is the lamplighter group, that is the wreath product of ℤ₂ and ℤ_{n}, and F is multiplication by a certain subgroup,
3) G is Hⁿ where H is non-abelian, and F selects a uniform coordinate and takes a uniform conjugate of it.
The obtained bounds for (1) and (2) are tight.
This work is motivated by and applied to problems in communication complexity. We consider the 3-party communication problem of deciding if the product of three group elements multiplies to the identity. We prove lower bounds for the groups above, which are tight for the affine and the lamplighter groups.

BibTeX - Entry

@InProceedings{gowers_et_al:LIPIcs.ITCS.2022.80,
  author =	{Gowers, W. T. and Viola, Emanuele},
  title =	{{Mixing in Non-Quasirandom Groups}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{80:1--80:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/15676},
  URN =		{urn:nbn:de:0030-drops-156761},
  doi =		{10.4230/LIPIcs.ITCS.2022.80},
  annote =	{Keywords: Groups, representation theory, mixing, communication complexity, quasi-random}
}

Keywords: Groups, representation theory, mixing, communication complexity, quasi-random
Collection: 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Issue Date: 2022
Date of publication: 25.01.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI