This research will develop methods for proving lower bounds on the complexity of general Boolean circuits for computing specific functions. Several directions appear promising. One is the topological approach of Sipser, where infinitary analogs suggest ways to apply concepts from descriptive set theory. The second is an approach suggested by Karchmer, Raz and Wigderson for obtaining high depth complexity by composing hard functions. The third is a method suggested by Razborov as a generalization of the approximation method he used to obtain monotone lower bounds.
