Skip to main content
main-content
Top

Hint

Swipe to navigate through the articles of this issue

07-05-2016 | Issue 2/2017

Theory of Computing Systems 2/2017

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

Journal:
Theory of Computing Systems > Issue 2/2017
Authors:
Louay Bazzi, Nagi Nahas
Important notes
Research supported by FEA URB grant Program Number 288309, American University of Beirut.

Abstract

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 = m c (assuming that \(e^{-\sqrt {m}}\leq p \leq p_{0}\), where p 0 > 0 is an absolute constant). In particular if p = n −Θ(1), the needed bias is 2−Ω(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 \mathbb {R}\) is such that and E[f l o w ] > 0 and f l o w (x) ≤ 0 for each x ∈ {0, 1} n such that F(x) = 0, then the L1-norm of the Fourier transform of f l o w is at least E[f l o w ]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.

Please log in to get access to this content

To get access to this content you need the following product:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 69.000 Bücher
  • über 500 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Umwelt
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Testen Sie jetzt 30 Tage kostenlos.

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 58.000 Bücher
  • über 300 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Testen Sie jetzt 30 Tage kostenlos.

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 50.000 Bücher
  • über 380 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Umwelt
  • Maschinenbau + Werkstoffe




Testen Sie jetzt 30 Tage kostenlos.

Literature
About this article

Other articles of this Issue 2/2017

Theory of Computing Systems 2/2017 Go to the issue

Premium Partner

    Image Credits