Document Open Access Logo

Mixing in Non-Quasirandom Groups

Authors W. T. Gowers, Emanuele Viola

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2022.80.pdf
  • Filesize: 0.53 MB
  • 9 pages

Document Identifiers

Author Details

W. T. Gowers
  • Collège de France, Paris, France
Emanuele Viola
  • Khoury College of Computer Sciences, Northeastern University, Boston, MA, USA

Funding

  • Viola, Emanuele: Supported by NSF CCF awards CCF-1813930 and CCF-2114116.

Acknowledgements

Emanuele Viola is grateful to Peter Ivanov for stimulating discussions.

Cite As Get BibTex

W. T. Gowers and Emanuele Viola. Mixing in Non-Quasirandom Groups. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 80:1-80:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ITCS.2022.80

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.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Combinatorics
  • Theory of computation → Communication complexity
Keywords
  • Groups
  • representation theory
  • mixing
  • communication complexity
  • quasi-random

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Andris Ambainis. Upper bounds on multiparty communication complexity of shifts. In Symp. on Theoretical Aspects of Computer Science (STACS), pages 631-642, 1996. Google Scholar
  2. Andris Ambainis and Satyanarayana V. Lokam. Improved upper bounds on the simultaneous messages complexity of the generalized addressing function. In Latin American Symposium on Theoretical Informatics (LATIN), pages 207-216, 2000. Google Scholar
  3. Tim Austin. Ajtai-Szemerédi theorems over quasirandom groups. In Recent trends in combinatorics, volume 159 of IMA Vol. Math. Appl., pages 453-484. Springer, [Cham], 2016. URL: https://doi.org/10.1007/978-3-319-24298-9_19.
  4. Tim Austin, Assaf Naor, and Alain Valette. The euclidean distortion of the lamplighter group. Discret. Comput. Geom., 44(1):55-74, 2010. URL: https://doi.org/10.1007/s00454-009-9162-6.
  5. László Babai, Anna Gál, Peter G. Kimmel, and Satyanarayana V. Lokam. Communication complexity of simultaneous messages. SIAM J. on Computing, 33(1):137-166, 2003. Google Scholar
  6. László Babai, Nikolay Nikolov, and László Pyber. Product growth and mixing in finite groups. In ACM-SIAM Symp. on Discrete Algorithms (SODA), pages 248-257, 2008. Google Scholar
  7. Ilya Baran, Erik D. Demaine, and Mihai Pǎtraşcu. Subquadratic algorithms for 3sum. Algorithmica, 50(4):584-596, 2008. Google Scholar
  8. Paul Beame, Matei David, Toniann Pitassi, and Philipp Woelfel. Separating deterministic from randomized multiparty communication complexity. Theory of Computing, 6(1):201-225, 2010. URL: https://doi.org/10.4086/toc.2010.v006a009.
  9. Michael Ben-Or and Richard Cleve. Computing algebraic formulas using a constant number of registers. SIAM J. on Computing, 21(1):54-58, 1992. Google Scholar
  10. Ashok K. Chandra, Merrick L. Furst, and Richard J. Lipton. Multi-party protocols. In 15th ACM Symp. on the Theory of Computing (STOC), pages 94-99, 1983. Google Scholar
  11. Martin Dietzfelbinger, Torben Hagerup, Jyrki Katajainen, and Martti Penttonen. A reliable randomized algorithm for the closest-pair problem. J. Algorithms, 25(1):19-51, 1997. Google Scholar
  12. W. T. Gowers. Quasirandom groups. Combinatorics, Probability & Computing, 17(3):363-387, 2008. Google Scholar
  13. W. T. Gowers. Generalizations of Fourier analysis, and how to apply them. Bull. Amer. Math. Soc. (N.S.), 54(1):1-44, 2017. URL: https://doi.org/10.1090/bull/1550.
  14. W. T. Gowers and Emanuele Viola. Interleaved group products. SIAM J. on Computing, 48(3):554-580, 2019. Special issue of FOCS 2016. Google Scholar
  15. Neil Immerman and Susan Landau. The complexity of iterated multiplication. Inf. Comput., 116(1):103-116, 1995. Google Scholar
  16. Kenneth Krohn, W. D. Maurer, and John Rhodes. Realizing complex Boolean functions with simple groups. Information and Control, 9:190-195, 1966. Google Scholar
  17. Eyal Kushilevitz and Noam Nisan. Communication complexity. Cambridge University Press, 1997. Google Scholar
  18. James R. Lee, Assaf Naor, and Yuval Peres. Trees and Markov convexity. Geom. Funct. Anal., 18(5):1609-1659, 2009. URL: https://doi.org/10.1007/s00039-008-0689-0.
  19. Shachar Lovett, Cristopher Moore, and Alexander Russell. Group representations that resist random sampling. Random Struct. Algorithms, 47(3):605-614, 2015. URL: https://doi.org/10.1002/rsa.20555.
  20. Eric Miles. Iterated group products and leakage resilience against NC¹. In ACM Innovations in Theoretical Computer Science conf. (ITCS), 2014. Google Scholar
  21. Eric Miles and Emanuele Viola. Shielding circuits with groups. In ACM Symp. on the Theory of Computing (STOC), 2013. Google Scholar
  22. David A. Mix Barrington. Bounded-width polynomial-size branching programs recognize exactly those languages in NC¹. J. of Computer and System Sciences, 38(1):150-164, 1989. Google Scholar
  23. Mihai Pǎtraşcu. Towards polynomial lower bounds for dynamic problems. In ACM Symp. on the Theory of Computing (STOC), pages 603-610, 2010. Google Scholar
  24. Pavel Pudlák, Vojtěch Rödl, and Jiří Sgall. Boolean circuits, tensor ranks, and communication complexity. SIAM J. on Computing, 26(3):605-633, 1997. Google Scholar
  25. Anup Rao and Amir Yehudayoff. Communication complexity. Cambridge University Press, 2019. https://homes.cs.washington.edu/ anuprao/pubs/book.pdf. Google Scholar
  26. Ran Raz. The BNS-Chung criterion for multi-party communication complexity. Computational Complexity, 9(2):113-122, 2000. Google Scholar
  27. Aner Shalev. Mixing, communication complexity and conjectures of Gowers and Viola. Combinatorics, Probability and Computing, pages 1-13, June 2016. arXiv:1601.00795. URL: https://doi.org/10.1017/S096354831600016X.
  28. Emanuele Viola. The communication complexity of addition. Combinatorica, pages 1-45, 2014. Google Scholar
  29. Emanuele Viola. Challenges in computational lower bounds. SIGACT News, Open Problems Column, 48(1), 2017. Google Scholar
  30. Emanuele Viola. Non-abelian combinatorics and communication complexity. SIGACT News, Complexity Theory Column, 50(3), 2019. Google Scholar
  31. Avi Wigderson. Representation theory of finite groups, and applications. Available at http://www.math.ias.edu/∼avi/TALKS/, 2010. Google Scholar
  32. Andrew Chi-Chih Yao. Some complexity questions related to distributive computing. In 11th ACM Symp. on the Theory of Computing (STOC), pages 209-213, 1979. Google Scholar
  33. Yufei Zhao. Group representations that resist worst-case sampling, 2017. URL: http://arxiv.org/abs/1705.04675.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact