Almost Optimal Dispersers

This paper )+O(1) Non-explicit [10,9] )+O(1) Lower bound [6, 9] 2. Preliminaries 2.1. Probability distributions and Random Variables A probability distribution X over , is a function X : ! [0; 1] such that \Sigma a2 X(a)= 1. We define the distance between two distributions using the l 1 norm: Definition 3. (statistical distance) Two distributions X and Y over the same space have statistical distance d(X; Y ) = 1 jX \Gamma Y j 1 = 1 a2 jX(a) \Gamma Y (a)j: If d(X;Y ) ffl we say X is ffl close to