Interleaved Group Products
From MaRDI portal
Publication:4634030
DOI10.1137/17M1126783zbMath1435.20015arXiv1804.09787MaRDI 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
representation theory; mixing; conjugacy class; communication complexity; special linear group; interleaved group product; iterated group products; quasi-random group
20C15: Ordinary representations and characters
20D60: Arithmetic and combinatorial problems involving abstract finite groups
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
20P05: Probabilistic methods in group theory
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
