Lower bounds for monotone span programs
Amos Beimel, Anna Gál, Mike Paterson · 1995
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 technique for proving lower bounds for monotone span programs, and prove a lower bound of Ω(m/sup 2.5/) for the 6-clique function. Our results improve on the previously known bounds for explicit functions.