DIMACS Theory of Computing Seminar


Lower Bounds for Monotone Span Programs


Anna Gal


DIMACS Seminar Room 431
CoRE Building
Rutgers University


4:30 PM
Thursday, November 16, 1995


Introduced by Karchmer and Wigderson in 1993, "span programs" are a linear algebraic model of computation with applications to lower bounds in other models (contact schemes, symmetric branching programs, formula size), and to cryptography (secret sharing).

We consider monotone span programs. Such a program P is specified by a vector space V, a special nonzero vector r\in V, and a family of subspaces W_1,...,W_n. With P we associate a monotone Booelan function f_P in n variables as follows: f_P(x_1,...,x_n)=1 precisely if the subspaces {W_i: x_i=1} span the vector r. The sum of the dimensions of the n subspaces W_1,...,W_n is called the size of P.

Every monotone Boolean function is representable as f_P for some P (over any field); the question is the minimum size. The relationship of this monotone model to monotone circuits is not clear, since it has free access to (nonmonotone) linear algebra. The known techniques for proving lower bounds for monotone circuits (Razborov and Haken's methods) do not apply to monotone span programs.

The talk will present results from two papers:

We develop a technique that allows to prove lower bounds for monotone span programs by considering a problem in extremal set theory. As a first application of the technique, we prove a lower bound of $\Omega(n^{2.5})$, for the 6-clique function.

This is joint work with Amos Beimel and Mike Paterson.

A very recent result demonstrates that this technique can yield superpolynomial lower bounds for explicit functions.

This is joint work with Laszlo Babai, Janos Kollar, Lajos Ronyai, Tibor Szabo and Avi Wigderson.

Document last modified on November 13, 1995