Extreme Rays of AND-Measures in Circuit Complexity

This paper is motivated by the problem of proving lower bounds on the formula size of boolean functions, which leads to lower bounds on circuit depth. We know that formula size is bounded from below by all formal complexity measures. Thus, we study formula size by investigating AND-measures, which are weakened forms of formal complexity measures. The collection of all AND-measures is a pointed polyhedral cone; we study the extreme rays of this cone in order to better understand AND-measures. From the extreme rays, we attempt to discover useful properties of AND-measures that may help in proving new lower bounds on formula size and circuit depth. This paper focuses on describing some of the properties of AND-measures, especially those that are extreme rays. Furthermore, it describes some algorithhms for finding the extreme rays