An Almost m-wise Independent Random Permutation of the Cube

DOI10.1017/S0963548300001917zbMath0865.60056OpenAlexW2127815364MaRDI QIDQ4715261

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

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

Related Items (6)

Fast Pseudorandom Functions Based on Expander Graphs ⋮ Derandomized constructions of \(k\)-wise (almost) independent permutations ⋮ On hereditarily indecomposable Banach spaces ⋮ Weak Oblivious Transfer from Strong One-Way Functions ⋮ Simple permutations mix well ⋮ The Complexity of Public-Key Cryptography

Cites Work

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

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