TR#: | CS0673 |

Class: | CS |

Title: | SIMPLE
CONSTRUCTIONS OF ALMOST {\em k}-wise INDEPENDENT RANDOM VARIABLES |

Authors: | N. Alon, O. Goldreich, J. Hastad, R. Peralta |

PDF - Revised | CS0673.revised.pdf |

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 + 0(1))($ log log $n + $ log $k + $log $\frac{1}{\varepsilon}$), where $\varepsilon$ 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 $\varepsilon < 1/(k\ \mbox{log}\ n)$). An additional advantage of our constructions is their simplicity. |

Copyright | The above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information |

Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/1991/CS/CS0673), rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1991

To the main CS technical reports page