Lower Bounds for Monotone Span Programs

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.

Authors

• Amos Beimel
• Anna Gál
• Mike Paterson

Keywords

• Polynomials
• Binary decision diagrams
• Computational modeling
• Cryptography
• Lower Bound
• Efficient Strategy
• Undirected
• Entailment
• Explicit Function
• Number Of Parties
• Boolean Function
• Program Size
• Triangular
• Value Function
• Loss Of Generality
• System Of Equations
• Size Classes
• Previous Lemma
• Complete Bipartite Graph