# DIMACS Theory of Computing Seminar

## Title:

Lower Bounds for Monotone Span Programs

## Speaker:

- Anna Gal
- IAS and DIMACS

## Place:

- DIMACS Seminar Room 431
- CoRE Building
- Rutgers University

## Time:

- 4:30 PM
- Thursday, November 16, 1995

## Abstract:

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