Small-Bias Sets for Nonabelian Groups

DOI10.1007/978-3-642-40328-6_31zbMATH Open1405.68436arXiv1304.5010OpenAlexW2963375715MaRDI QIDQ2851876FDOQ2851876

Authors: Sixia Chen, Cristopher Moore, Alexander Russell 

Publication date: 4 October 2013

Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Abstract: In analogy with epsilon-biased sets over Z_2^n, we construct explicit epsilon-biased sets over nonabelian finite groups G. That is, we find sets S subset G such that | Exp_{x in S} rho(x)| <= epsilon for any nontrivial irreducible representation rho. Equivalently, such sets make G's Cayley graph an expander with eigenvalue |lambda| <= epsilon. The Alon-Roichman theorem shows that random sets of size O(log |G| / epsilon^2) suffice. For groups of the form G = G_1 x ... x G_n, our construction has size poly(max_i |G_i|, n, epsilon^{-1}), and we show that a set S subset G^n considered by Meka and Zuckerman that fools read-once branching programs over G is also epsilon-biased in this sense. For solvable groups whose abelian quotients have constant exponent, we obtain epsilon-biased sets of size (log |G|)^{1+o(1)} poly(epsilon^{-1}). Our techniques include derandomized squaring (in both the matrix product and tensor product senses) and a Chernoff-like bound on the expected norm of the product of independently random operators that may be of independent interest.

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

Recommendations

• A structure theorem for small sumsets in nonabelian groups
• On finite subsets of nonabelian groups with small doubling.
• On finite sets of small tripling or small alternation in arbitrary groups
• Random groups and nonarchimedean lattices
• On a conjecture of the small Davenport constant for finite groups
• Small-Bias Spaces for Group Products
• On groups with relatively small normalizers of nonabelian subgroups.
• scientific article; zbMATH DE number 1315275
• scientific article; zbMATH DE number 4208435
• Bias of group generators in finite and profinite groups: known results and open problems

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Randomized algorithms (68W20) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25)

Cited In (10)

• Attacking quantum hashing. Protocols and their cryptanalysis
• Geometry of random Cayley graphs of abelian groups
• Quantum hashing for finite abelian groups
• Analysis of properties of quantum hashing
• Expanding Generating Sets for Solvable Permutation Groups
• Small-Bias Spaces for Group Products
• Quantum Hashing and Fingerprinting for Quantum Cryptography and Computations
• The remote point problem, small bias spaces, and expanding generator sets
• Near-optimal expanding generator sets for solvable permutation groups
• Classical and Quantum Computations with Restricted Memory

This page was built for publication: Small-Bias Sets for Nonabelian Groups

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2851876)