Prof. Amos Beimel
Know all about my research
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 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 Ω(m2.5) for the 6-clique function. Our results improve on the previously known bounds for explicit functions.
| Publication language | English |
| Pages | 29-45 |
| Journal | Computational Complexity |
| Volume | 6 |
| Issue number | 1 |
| Publication status | Published - 01.01.1996 |
Keywords
Lower bounds
Monotone complexity classes
Secret sharing
Span programs
ASJC Scopus subject areas
Theoretical Computer Science
General Mathematics
Computational Theory and Mathematics
Computational Mathematics
