Small-bias probability spaces have wide applications in pseudorandomness which naturally leads to the study of their limitations. Constructing a polynomial complexity hitting set for read-once CNF formulas is a basic open problem in pseudorandomness. We show in this paper that this goal is not achievable using small-bias spaces. Namely, we ... more >>>
A classical bound in Information Theory asserts that small L_1-distance between probability distributions implies small difference in Shannon entropy, but the converse need not be true. We show that if a probability distribution on \{0,1\}^n has small-bias, then the converse holds for its weight distribution in the proximity of the ... more >>>