•  
  •  
 

Abstract

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.

Author Bio

Edward Lui is a student in the Computer Science and Mathematics Combined Honours program at the University of British Columbia. This paper is based on the work that he did in the summer of 2007 under the NSERC Undergraduate Student Research Award (USRA). He will be graduating in April 2009 and plans to pursue a PhD in Computer Science. His main research interests include complexity theory, graph theory, and algorithms for graph-theoretic and combinatorial problems.

Download

Share

COinS