### Abstract

We present three alternative simple constructions of small probability spaces on n bits for which any k bits are almost independent. The number of bits used to specify a point in the sample space is (2 + o(1)) (log log n + k/2 + log k + log 1/ϵ), where ϵ is the statistical difference between the distribution induced on any k bit 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/(k log n)). An additional advantage of our constructions is their simplicity.

Original language | English (US) |
---|---|

Pages (from-to) | 289-304 |

Number of pages | 16 |

Journal | Random Structures & Algorithms |

Volume | 3 |

Issue number | 3 |

DOIs | |

State | Published - 1992 |

Externally published | Yes |

### All Science Journal Classification (ASJC) codes

- Software
- Mathematics(all)
- Computer Graphics and Computer-Aided Design
- Applied Mathematics

### Keywords

- Probabilistic computation
- removing randomness
- shiftregister sequences
- small probability spaces

## Fingerprint Dive into the research topics of 'Simple Constructions of Almost k‐wise Independent Random Variables'. Together they form a unique fingerprint.

## Cite this

Alon, N., Goldreich, O., Håstad, J., & Peralta, R. (1992). Simple Constructions of Almost k‐wise Independent Random Variables.

*Random Structures & Algorithms*,*3*(3), 289-304. https://doi.org/10.1002/rsa.3240030308