期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1995
卷号：1995
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：The model of span programs is a linear algebraic model of
computation. Lower bounds for span programs imply lower bounds for
contact schemes, symmetric branching programs and for formula size.
Monotone span programs correspond also to linear secret-sharing schemes.
We present a new technique for proving lower bounds for monotone span
programs. The main result proved here yields quadratic lower bounds for
the size of monotone span programs, improving on the largest previously
known bounds for explicit functions. The bound is asymptotically tight
for the function corresponding to a class of 4-cliques.
