Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Nagi Nahas:

TR13-034 | 2nd March 2013
Louay Bazzi, Nagi Nahas

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 ... more >>>

ISSN 1433-8092 | Imprint