Small-Bias is Not Enough to Hit Read-Once CNF

详细信息    查看全文

• 作者：Louay Bazzi ; Nagi Nahas
• 关键词：Pseudorandomness ; Hitting set ; Read ; once CNF formulas ; Small ; bias ; Harmonic analysis
• 刊名：Theory of Computing Systems
• 出版年：2017
• 出版时间：February 2017
• 年：2017
• 卷：60
• 期：2
• 页码：324-345
• 全文大小：
• 刊物类别：Computer Science
• 刊物主题：Theory of Computation; Computational Mathematics and Numerical Analysis;
• 出版者：Springer US
• ISSN：1433-0490
• 卷排序：60

文摘

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 {0, 1}n such that δ = 2−Ω(logm log(1/p)) and no element in the support of μ satisfies F, where n = mc (assuming that \(e^{-\sqrt {m}}\leq p \leq p_{0}\), where p₀ > 0 is an absolute constant). In particular if p = n−Θ(1), the needed bias is 2−Ω(log2n), 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 \mathbb {R}\) is such that and E[f_low] > 0 and f_low(x) ≤ 0 for each x ∈ {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Ω(logm 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 Θ(1) probability of acceptance.