An Almost m-wise Independent Random Permutation of the Cube
Author:
- 1 June 1996
- journal article
- research article
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 5 (2) , 119-130
Abstract
We describe a very simple method of randomly permuting the cube {0, 1}n such that the sample space is very small, but, given any m distinct points in {0, 1}n, the images of those points under the random permutation are approximately uniformly distributed over all sequences of m distinct points.Keywords
This publication has 9 references indexed in Scilit:
- Pseudorandom generators for space-bounded computationCombinatorica, 1992
- Improved Bounds for Mixing Rates of Markov Chains and Multicommodity FlowCombinatorics, Probability and Computing, 1992
- Simple Constructions of Almost k‐wise Independent Random VariablesRandom Structures & Algorithms, 1992
- Pseudorandom bits for constant depth circuitsCombinatorica, 1991
- Geometric Bounds for Eigenvalues of Markov ChainsThe Annals of Applied Probability, 1991
- Approximate Inclusion-ExclusionCombinatorica, 1990
- Fast uniform generation of regular graphsTheoretical Computer Science, 1990
- Approximating the PermanentSIAM Journal on Computing, 1989
- How to Construct Pseudorandom Permutations from Pseudorandom FunctionsSIAM Journal on Computing, 1988