Applications of matrix methods to the theory of lower bounds in computational complexity

We present some criteria for obtaining lower bounds for the formula size of Boolean functions. In the monotone case we get the boundn^(logn) for the function MINIMUM COVER using methods considerably simpler than all previously known. In the general case we are only able to prove that the criteria yield an exponential lower bound when applied to almost all functions. Some connections with graph complexity and communication complexity are also given.