Title :
Lower bounds for monotone span programs
Author :
Beimel, Amos ; Gál, Anna ; Paterson, Max
Author_Institution :
Dept. of Comput. Sci., Technion-Israel Inst. of Technol., Haifa, Israel
Abstract :
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.
Keywords :
computation theory; cryptography; programming theory; formula size; linear algebraic model; lower bounds; monotone span programs; secret-sharing; span programs; symmetric branching; Binary decision diagrams; Computational modeling; Cryptography; Polynomials;
Conference_Titel :
Foundations of Computer Science, 1995. Proceedings., 36th Annual Symposium on
Conference_Location :
Milwaukee, WI, USA
Print_ISBN :
0-8186-7183-1
DOI :
10.1109/SFCS.1995.492669
