The communication complexity of interleaved group products

DOI10.1145/2746539.2746560zbMath1321.94063OpenAlexW1995343556MaRDI QIDQ2941525

Emanuele Viola, Timothy Gowers

Publication date: 21 August 2015

Published in: Proceedings of the forty-seventh annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2746539.2746560

zbMATH Keywords

representation theorymixingconjugacy classcommunication complexityspecial linear groupinterleaved group productiterated group productsquasirandom group

Mathematics Subject Classification ID

Cryptography (94A60) Probabilistic methods in group theory (20P05)

Related Items (4)

Unnamed Item ⋮ Mixing, Communication Complexity and Conjectures of Gowers and Viola ⋮ Conjugacy classes, growth and complexity ⋮ Interleaved Group Products

Uses Software

• Graphs

Cites Work

• Unnamed Item
• Ramsey partitions and proximity data structures
• On sparse spanners of weighted graphs
• Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
• On Approximate Distance Labels and Routing Schemes with Affine Stretch
• Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
• Approximate distance oracles
• Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
• Near-Linear Time Construction of Sparse Neighborhood Covers
• Shortest-path queries in static networks
• Approximate distance oracles with constant query time
• Automata, Languages and Programming

This page was built for publication: The communication complexity of interleaved group products