TSpace

Abstract (summary): Razborov introduced an elegant rank-based complexity measure for proving lower bounds on the monotone formula complexity of boolean functions. Later work by Gal showed that Razborov's rank measure also provides lower bounds on monotone switching networks, which measure space complexity, and monotone span programs, which are an elegant complexity measure that have connections to cryptography. Despite this, the only lower bounds known for the rank measure are the original n^log n bounds for function computable in NP due to Razborov. In this thesis, we give a new analysis of the rank measure; in particular, connecting it to the Nullstellensatz degree from propositional proof complexity. This ultimately allows us to ``lift'' Nullstellensatz degree lower bounds to rank measure lower bounds in a generic way, and using this lifting theorem we are able to prove a variety of new lower bounds in monotone complexity theory, as well as obtaining new proofs of many old lower bounds. To prove our results we introduce several technical tools which we hope will have other applications. In particular, we introduce a new algebraic complexity measure called the algebraic gap complexity which is crucial in our reductions, as well as a generic way to transform multilinear polynomials into matrices such that the rank of the matrix can be directly calculated from the monomials in the polynomial (this generalizes an earlier result of Sherstov.