Lower Bounds on Formula Size of Boolean Functions using Hypergraph-Entropy

Korner [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 \Omega\Gamma 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 ..