Small-bias is not enough to hit read-once CNF
type: Item
instance of: scholarly article
title: Small-bias is not enough to hit read-once CNF
zbMATH Open document ID: 1364.68300
author: Louay Bazzi
author: Nagi H. Nahas
published in: Theory of Computing Systems
publication date: 2017-03-31T00:00:00Z
Mathematics Subject Classification ID: 68Q87
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 6699123
zbMATH Keywords: pseudorandomness
zbMATH Keywords: hitting set
zbMATH Keywords: read-once CNF formulas
zbMATH Keywords: small-bias
zbMATH Keywords: harmonic analysis
MaRDI profile type: Publication
full work available at URL: s00224-016-9680-6
OpenAlex ID: W2345543786
cites work: Small Sample Spaces Cannot Fool Low Degree Polynomials
cites work: A new general derandomization method
cites work: Simple Constructions of Almost k-wise Independent Random Variables
cites work: Polylogarithmic Independence Can Fool DNF Formulas
cites work: Polylogarithmic independence fools AC 0 circuits
cites work: How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
cites work: Improved Pseudorandom Generators for Depth 2 Circuits
cites work: A Simple Proof of Bazzi’s Theorem
cites work: Q4526985
cites work: Approximate inclusion-exclusion
cites work: Pseudorandom Bit Generators That Fool Modular Sums
cites work: Pseudorandom bits for constant depth circuits
cites work: Small-Bias Spaces for Group Products
cites work: Small-Bias Probability Spaces: Efficient Constructions and Applications
cites work: Hardness vs randomness
cites work: Almost k-Wise Independent Sets Establish Hitting Sets for Width-3 1-Branching Programs
cites work: Q4061445
cites work: Two results on polynomial interpolation in equally spaced points
DOI: 10.1007/S00224-016-9680-6
description: scientific article; zbMATH DE number 6699123