Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with secret-sharing:
TR95-001 | 1st January 1995
Amos Beimel, Anna Gal, Michael S. Paterson

Lower Bounds for Monotone Span Programs

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 ... more >>>

ISSN 1433-8092 | Imprint