An Almost m-wise Independent Random Permutation of the Cube

DOI10.1017/S0963548300001917MaRDI QIDQ4715261zbMATH OpenOpenAlexFDO

Authors W. Timothy Gowers

Publication date 12 November 1996

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1017/s0963548300001917

zbMATH Keywords

random permutationrapidly mixing Markov chains

Mathematics Subject Classification ID

Combinatorial probability (60C05) Sums of independent random variables; random walks (60G50)

Recommendations

• Automata, Languages and Programming
• Simple permutations mix even better
• Simple permutations mix well
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Derandomized constructions of \(k\)-wise (almost) independent permutations

Cites work

• Approximate inclusion-exclusion
• Approximating the Permanent
• Fast uniform generation of regular graphs
• Geometric bounds for eigenvalues of Markov chains
• How to Construct Pseudorandom Permutations from Pseudorandom Functions
• Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
• Pseudorandom bits for constant depth circuits
• Pseudorandom generators for space-bounded computation
• Simple Constructions of Almost k-wise Independent Random Variables

Cited in

(13)

• Derandomized constructions of \(k\)-wise (almost) independent permutations
• Simple permutations mix well
• Weak oblivious transfer from strong one-way functions
• Fast pseudorandom functions based on expander graphs
• Shift-Generated Random Permutations and The M/D/1 Queue
• The Complexity of Public-Key Cryptography
• On hereditarily indecomposable Banach spaces
• Complexity theory. Abstracts from the workshop held June 2--7, 2024
• Pseudorandomness properties of random reversible circuits
• Towards general-purpose program obfuscation via local mixing
• Dynamics of pseudoentanglement
• When simple permutations mix poorly. Limited independence does not imply pseudorandomness
• Efficient quantum pseudorandomness from Hamiltonian phase states

This page was built for publication: An Almost m-wise Independent Random Permutation of the Cube

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