Lower Bounds on Formula Size of Boolean Functions Using Hypergraph Entropy
Ilan Newman, Avi Wigderson · SIAM Journal on Discrete Mathematics · 1995
Körner defined the notion of graph entropy. He used it 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 do not apply.