An Overview of Lower Bound Techniques in Monotone Boolean Function Complexity

Paul Dunne

Abstract

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.