Prof. Amos Beimel

Span programs provide a linear algebraic model of computation. Lower bounds for span programs imply lower bounds for formula size, symmetric branching programs and for 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, and prove a lower bound of Ω(m^2.5) for the 6-clique function. Our results improve on the previously known bounds for explicit functions.