Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR13-034 | 2nd March 2013 00:08

Small-bias is not enough to hit read-once CNF



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 $\delta$-biased distribution $\mu$ on $\lbrace 0,1 \rbrace^{n}$ such that $\delta = 2^{-\Omega(\log{m} \log{({1}/{p})})}$ and no element in the support of $\mu$ satisfies $F$, where $n=mc$ (assuming that $2^{-m^{0.3}}\leq p \leq p_0$, where $p_0>0$ is an absolute constant). In particular if $p = n^{-\Theta(1)}$, the needed bias is $2^{-\Omega( \log^2{n})}$, which requires a hitting set of size $2^{\Omega(\log^2{n})}$. Our lower bound on the needed bias is asymptotically tight. The dual version of our result asserts that if $f_{low}:\{0,1\}^n\rightarrow R$ is such that and $E[f_{low}]>0$ and $f_{low}(x)\leq 0$ for each $x\in \{0,1\}^n$ such that $F(x) = 0$, then the $L1$-norm of the Fourier transform of $f_{low}$ is at least $E[f_{low}]2^{\Omega(\log{m} \log{({1}/{p})})}$. 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 $\Theta(1)$ probability of acceptance.

ISSN 1433-8092 | Imprint