DocumentCode
2200657
Title
On span programs
Author
Karchmer, M. ; Wigderson, A.
Author_Institution
Dept. of Math., MIT, Cambridge, MA, USA
fYear
1993
fDate
18-21 May 1993
Firstpage
102
Lastpage
111
Abstract
A linear algebraic model of computation the span program, is introduced, and several upper and lower bounds on it are proved. These results yield applications in complexity and cryptography. The proof of the main connection, between span programs and counting branching programs, uses a variant of Razborov´s general approximation method
Keywords
computational complexity; cryptography; linear algebra; Razborov´s general approximation method; complexity; counting branching programs; cryptography; linear algebraic model of computation; lower bounds; span programs; upper bounds;
fLanguage
English
Publisher
ieee
Conference_Titel
Structure in Complexity Theory Conference, 1993., Proceedings of the Eighth Annual
Conference_Location
San Diego, CA
Print_ISBN
0-8186-4070-7
Type
conf
DOI
10.1109/SCT.1993.336536
Filename
336536
Link To Document