ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR95-001 | 1st January 1995 00:00

Lower Bounds for Monotone Span Programs

RSS-Feed




TR95-001
Authors: Amos Beimel, Anna Gal, Michael S. Paterson
Publication: 1st January 1995 00:00
Downloads: 794
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint