Variable Influences in Conjunctive Normal Forms

Abstract We provide an upper bound on the total influence of Boolean functions defined by k -cnfs. Our bound is nearly optimal. We achieve it by an extension and appropriate use of an algorithm of Paturi, Pudlák, and Zane. We also discuss applications to prove and compute lower bounds for the maximum clause width k.

Authors

• Patrick Traxler

Keywords

No keywords are indexed for this paper.