Simple permutations mix even better

DOI10.1002/RSA.20194MaRDI QIDQ3503604zbMATH OpenOpenAlexFDO

Authors Alex Brodsky, Shlomo Hoory

Publication date 5 June 2008

Published in Random Structures \& Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

cryptographyreversible computationmulticommodity flowmixing-time\(k\)-wise independent permutations

Mathematics Subject Classification ID

Permutations, words, matrices (05A05)

Abstract: We study the random composition of a small family of O(n^3) simple permutations on {0,1}^n. Specifically we ask how many randomly selected simple permutations need be composed to yield a permutation that is close to k-wise independent. We improve on the results of Gowers 1996 and Hoory, Magen, Myers and Rackoff 2004, and show that up to a polylogarithmic factor, n^2*k^2 compositions of random permutations from this family suffice. In addition, our results give an explicit construction of a degree O(n^3) Cayley graph of the alternating group of 2^n objects with a spectral gap Omega(2^{-n}/n^2), which is a substantial improvement over previous constructions.

Recommendations

• Automata, Languages and Programming
• Simple permutations mix well
• Odd permutations are nicer than even ones
• scientific article; zbMATH DE number 1978940
• Prolific permutations
• Permutads
• scientific article; zbMATH DE number 1943960
• Permutations

Cites work

• scientific article; zbMATH DE number 2163011 (Why is no real title available?)
• scientific article; zbMATH DE number 1885142 (Why is no real title available?)
• A new family of Cayley expanders (?)
• A universal two-bit gate for quantum computation
• Automata, Languages and Programming
• Diameter, covering index, covering radius and eigenvalues
• Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
• Theory of Cryptography

Cited in

(16)

• An Almost m-wise Independent Random Permutation of the Cube
• Layout graphs, random walks and the t-wise independence of SPN block ciphers
• Dynamics of pseudoentanglement
• scientific article; zbMATH DE number 5542483 (Why is no real title available?)
• Fast pseudorandom functions based on expander graphs
• Simple permutations mix well
• The \(t\)-wise independence of substitution-permutation networks
• Random quantum circuits are approximate 2-designs
• Pseudorandomness properties of random reversible circuits
• Derandomized constructions of \(k\)-wise (almost) independent permutations
• Efficient approximate unitary designs from random Pauli rotations
• Local random quantum circuits are approximate polynomial-designs
• Automata, Languages and Programming
• Complexity theory. Abstracts from the workshop held June 2--7, 2024
• scientific article; zbMATH DE number 1978940 (Why is no real title available?)
• Quantum statistical mechanics of encryption: reaching the speed limit of classical block ciphers

This page was built for publication: Simple permutations mix even better

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