On Extremal k-CNF Formulas

The average sensitivity of a Boolean function is the expectation, given a uniformly random input, of the number of input bits which when flipped change the output of the function. A k-CNF is a CNF in which every clause contains at most k literals. It has recently been shown by the author [Amano, K., Tight Bounds on the Average Sensitivity of k-CNF, Theory of Computing, 7(4) (2011), 45–48] that the average sensitivity of a k-CNF is at most k. This bound is tight since the parity function on k variables has the average sensitivity k. s paper, we consider the problem to determine the extremal formulas achieving this bound. We give a class of such formulas that contains a double exponential (in k) number of non-isomorphic ones. This class captures all formulas, with only one exception, that we have obtained so far. We also give the complete list for k = 2 and 3 as well as several structural properties of such extremal formulas.