__
TR02-007 | 14th January 2002 00:00
__

#### Monotone complexity and the rank of matrices

**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

Comment #1
Authors:

Anna Gal
Accepted on: 4th February 2002 11:07

Downloads: 857

Keywords:

**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.