All reports by Author Louay Bazzi:

__
TR14-112
| 23rd August 2014
__

Louay Bazzi#### Entropy of weight distributions of small-bias spaces and pseudobinomiality

Revisions: 1

__
TR13-034
| 2nd March 2013
__

Louay Bazzi, Nagi Nahas#### Small-bias is not enough to hit read-once CNF

Louay Bazzi

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 >>>

Louay Bazzi, Nagi Nahas

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 >>>