Under the auspices of the Computational Complexity Foundation (CCF)
The model of span programs is a linear algebraic model of
computation. Lower bounds for span programs imply lower bounds for
contact schemes, symmetric branching programs and for formula size.
Monotone span programs correspond also to linear secret-sharing schemes.
We present a new technique for proving lower bounds for monotone span
programs. The main result proved here yields quadratic lower bounds for
the size of monotone span programs, improving on the largest previously
known bounds for explicit functions. The bound is asymptotically tight
for the function corresponding to a class of 4-cliques.