Perfect hashing, graph entropy, and circuit complexity
Ilan Newman, Prabhakar L. Ragde, Avi Wigderson · 2002
It is shown that approximate compaction can be efficiently performed in constant parallel time using perfect hash functions. This allows it to be shown that polylogarithmic-threshold functions are in linear AC/sup o/. Next, it is shown that the information-theoretic notion of graph entropy captures some aspect of the difficulty of computing Boolean functions. This is used to derive superlinear lower bounds on the formula size of threshold and other simple Boolean functions.>