Abstract:
The rank of a matrix has been used a number of times to prove lower bounds on various types of complexity. In particular it has been used for the size of monotone formulas and monotone span programs. In most cases that this approach was used, there is not a single matrix associated with the function in question, but one has to minimize the rank over a set of matrices (eg., \cite{razborov,gal}). Usually, this makes the techniques very difficult to apply. In this note we define a certain combinatorial structure that enables us to use the rank lower bound directly. We shall not prove new lower bound, we only show that some previous lower bounds on monotone span programs can be simply derived using this structure. It is open whether our approach can produce better lower bounds.

Comment #1 to TR02-007 | 4th February 2002 11:07

Answer to the open problem of ECCC TR02-007 Comment on: TR02-007

Abstract:
The following open problem was stated in ECCC TR02-007 (Pavel Pudlak: Monotone complexity and the rank of matrices). Let A be a family of subsets of [n], and B be a family of k-tuples of subsets of [n], such that for each subset a in A and each k-tuple in B, the subset a has a nonempty intersection with exactly one member of the k-tuple. Associate with the sets A and B a matrix specifying the location of the intersection for each (subset, k-tuple) pair. The question was, is it possible that the rank of the associated matrix is larger than n^O(logn) for some sets A,B. We show that the answer to this question is no.