Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



TR02-007 | 14th January 2002 00:00

Monotone complexity and the rank of matrices


Authors: Pavel Pudlak
Publication: 14th January 2002 18:20
Downloads: 968


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: 906


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.

ISSN 1433-8092 | Imprint