Lower bounds on formula size of Boolean functions using hypergraph entropy

Körner [7] defined the notion of graph-entropy. He used it in [8] to simplify the proof of the Fredman-Komlos lower bound for the family size of perfect hash functions. We use this information theoretic notion to obtain a general method for formula size lower bounds. This method can be applied to low-complexity functions for which the other known general methods ([11, 12, 3] and see also [17] ) do not apply. Specifically the results are: 1. A new general lower bound on the formula size of quadratic Boolean functions. 2. As a corollary we get an Ω(n 2 logn) lower bound for the function that decides whether a graph of n vertices has a cycle of length four, and to the function that decides whether a graph has a vertex of degree at least two. 3. A simple proof of a result of Krichevskii, [10] , stating that the formula size for the threshold-2 Boolean function with n variables is at least n log n. 4. A simple proof of a lower bound first proved by Snir, [16], stating that a formula for n- variable threshold-k function, where all ∧ gates have fan in k, has the size of log n − log(k − 1) n Ω ( n) = Ω(nk log log k − log(k − 1) k) Notation: 1. Let X be a finite set, interpreted as Boolean variables. A formula is a rooted tree whose leaves are labeled with members of X or their negations, and whose internal nodes are labeled with the Boolean operations AND, OR. The root of the tree computes a Boolean function f; {0, 1} X ↦ → {0, 1} in the natural way. If no negations appear, w