Mixing, Communication Complexity and Conjectures of Gowers and Viola

DOI10.1017/S096354831600016XzbMath1402.20027WikidataQ122889954 ScholiaQ122889954MaRDI QIDQ5366956

Aner Shalev

Publication date: 10 October 2017

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Simple groups: alternating groups and groups of Lie type (20D06) Probabilistic methods in group theory (20P05)

Related Items

Corrigendum to ‘Mixing, Communication Complexity and Conjectures of Gowers and Viola’, Some remarks on global/local conjectures, Conjugacy classes, growth and complexity, Interleaved Group Products

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The Waring problem for finite simple groups.
• Mixing and generation in simple groups.
• Word maps, conjugacy classes, and a noncommutative Waring-type theorem.
• On the minimal degrees of projective representations of the finite Chevalley groups
• Fuchsian groups, finite simple groups and representation varieties.
• Fuchsian groups, coverings of Riemann surfaces, subgroup growth, random quotients and random walks.
• Products of conjugacy classes in groups
• Bounds on the number and sizes of conjugacy classes in finite Chevalley groups with applications to derangements
• The communication complexity of interleaved group products
• Products of conjugacy classes and fixed point spaces
• Quasirandom Groups
• The complexity of promise problems with applications to public-key cryptography
• On the conjectures of J. Thompson and O. Ore
• Character degrees and random walks in finite groups of Lie type
• Shielding circuits with groups