An Overview of Lower Bound Techniques in Monotone Boolean Function Complexity
In 1985, Razborov discovered the `Method of Approximations',
an approach that led to the first super-polynomial lower
bounds on the monotone circuit size of explcitly defined
Boolean functions. Over the last few years there have been
further advances in the theory of monotone circuit complexity,
resulting in extensions to Razborov's approach and the
discovery of new lower bound arguments, e.g. Haken's `bottleneck
counting' technique, Finite Limits, etc. In this talk, an
overview and comparison of these approaches will be presented.
The potential for obtaining lower bounds on general Boolean
networks will also be considered.