Simple Constructions of Almost k‐wise Independent Random Variables
- 1 January 1992
- journal article
- research article
- Published by Wiley in Random Structures & Algorithms
- Vol. 3 (3) , 289-304
- https://doi.org/10.1002/rsa.3240030308
Abstract
We present three alternative simple constructions of small probability spaces onnbits for which anykbits are almost independent. The number of bits used to specify a point in the sample space is (2 +o(1)) (log logn+k/2 + logk+ log 1/ϵ), where ϵ is the statistical difference between the distribution induced on anykbit locations and the uniform distribution. This is asymptotically comparable to the construction recently presented by Naor and Naor (our size bound is better as long as ϵ < 1/(klogn)). An additional advantage of our constructions is their simplicity.Keywords
This publication has 21 references indexed in Scilit:
- Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphsIEEE Transactions on Information Theory, 1992
- A parallel algorithmic version of the local lemmaRandom Structures & Algorithms, 1991
- On the power of two-point based samplingJournal of Complexity, 1989
- Recognizing primes in random polynomial timePublished by Association for Computing Machinery (ACM) ,1987
- Deterministic simulation in LOGSPACEPublished by Association for Computing Machinery (ACM) ,1987
- A fast and simple randomized parallel algorithm for the maximal independent set problemJournal of Algorithms, 1986
- Almost all primes can be quickly certifiedPublished by Association for Computing Machinery (ACM) ,1986
- Explicit constructions of linear-sized superconcentratorsJournal of Computer and System Sciences, 1981
- Probabilistic algorithm for testing primalityJournal of Number Theory, 1980
- A Fast Monte-Carlo Test for PrimalitySIAM Journal on Computing, 1977