The Library
Lower bounds for monotone span programs
Tools
UNSPECIFIED (1996) Lower bounds for monotone span programs. COMPUTATIONAL COMPLEXITY, 6 (1). pp. 29-45. ISSN 1016-3328.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
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 contact schemes. Monotone span programs correspond also to linear secret-sharing schemes. We present a new technique for proving lower bounds for monotone span programs. We prove a lower bound of Omega(m(2.5)) for the 6-clique function. Our results improve on the previously known bounds for explicit functions.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software Q Science > QA Mathematics |
||||
Journal or Publication Title: | COMPUTATIONAL COMPLEXITY | ||||
Publisher: | BIRKHAUSER VERLAG AG | ||||
ISSN: | 1016-3328 | ||||
Official Date: | 1996 | ||||
Dates: |
|
||||
Volume: | 6 | ||||
Number: | 1 | ||||
Number of Pages: | 17 | ||||
Page Range: | pp. 29-45 | ||||
Publication Status: | Published |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |