Interleaved Group Products

DOI10.1137/17M1126783zbMath1435.20015arXiv1804.09787OpenAlexW2963290299MaRDI QIDQ4634030

Emanuele Viola, Timothy Gowers

Publication date: 7 May 2019

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1804.09787

zbMATH Keywords

representation theorymixingconjugacy classcommunication complexityspecial linear groupinterleaved group productiterated group productsquasi-random group

Mathematics Subject Classification ID

Ordinary representations and characters (20C15) Arithmetic and combinatorial problems involving abstract finite groups (20D60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Probabilistic methods in group theory (20P05)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Mixing and generation in simple groups.
• Random oracles separate PSPACE from the polynomial-time hierarchy
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
• The BNS lower bound for multi-party protocols is nearly optimal
• The complexity of iterated multiplication
• A minimal model for secure computation (extended abstract)
• The NOF Multiparty Communication Complexity of Composed Functions
• The communication complexity of interleaved group products
• Iterated group products and leakage resilience against NC1
• How to Compute in the Presence of Leakage
• Quasirandom Groups
• Protecting Circuits from Leakage: the Computationally-Bounded and Noisy Cases
• Problems complete for deterministic logarithmic space
• Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
• Computing Algebraic Formulas Using a Constant Number of Registers
• Boolean Circuits, Tensor Ranks, and Communication Complexity
• Communication Complexity of Simultaneous Messages
• Upper bounds on multiparty communication complexity of shifts
• Communication Complexity
• Communication Complexity and Quasi Randomness
• Mixing, Communication Complexity and Conjectures of Gowers and Viola
• Advances in Cryptology - CRYPTO 2003
• Shielding circuits with groups
• Realizing complex boolean functions with simple groups
• Cryptography in $NC^0$
• Number of Points of Varieties in Finite Fields
• Theory of Cryptography
• The BNS-Chung criterion for multi-party communication complexity