Better Lower Bounds for Monotone Threshold Formulas

摘要

We show that every monotone formula that computes the threshold function THk, n, 2⩽k⩽n/2, has size at least ⌊k/2⌋ n log(n/(k−1)). The same lower bound is shown to hold in the stronger monotone directed contact networks model.