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 show that for each read-once CNF formula F with probability of acceptance p and with m clauses each of size c, there exists a -biased distribution on 01n such that =2?(logmlog(1p)) and no element in the support of satisfies F, where n=mc (assuming that 2?m03pp0, where 0">p00 is an absolute constant). In particular if p=n?(1), the needed bias is 2?(log2n), which requires a hitting set of size 2(log2n). Our lower bound on the needed bias is asymptotically tight. The dual version of our result asserts that if flow:01nR is such that and 0">E[flow]0 and flow(x)0 for each x01n such that F(x)=0, then the L1-norm of the Fourier transform of flow is at least E[flow]2(logmlog(1p)) . Our result extends a result due to De, Etesami, Trevisan, and Tulsiani (APPROX-RANDOM 2010) who proved that the small-bias property is not enough to obtain a polynomial complexity PRG for a family of read-once formulas of (1) probability of acceptance.
展开▼
