עמוס ביימל

Span programs provide a linear algebraic model of computation. Lower bounds for span programs imply lower bounds for formula size, symmetric branching programs, and contact schemes. Monotone span programs correspond also to linear secret-sharing schemes. We present a new technique for proving lower bounds for monotone span programs. We prove a lower bound of Ω(m^2.5) for the 6-clique function. Our results improve on the previously known bounds for explicit functions.