On span programs
Top Cited Papers
- 30 December 2002
- proceedings article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 102-111
- https://doi.org/10.1109/sct.1993.336536
Abstract
We introduce a linear algebraic model of computa- tion, the Span Program, and prove several upper and lower bounds on it. These results yield the following applications in complexity and cryptography: SL L (a weak Logspace analogue of NP P ).Keywords
This publication has 17 references indexed in Scilit:
- Two remarks on the power of countingPublished by Springer Nature ,2005
- Monotone ComplexityPublished by Cambridge University Press (CUP) ,1992
- Structure and importance of logspace-MOD classTheory of Computing Systems, 1992
- A combinatorial approach to complexityCombinatorica, 1992
- Lower bounds of the complexity of symmetric boolean functions of contact-rectifier circuitsMathematical Notes, 1990
- Lower bounds to the complexity of symmetric Boolean functionsTheoretical Computer Science, 1990
- Applications of matrix methods to the theory of lower bounds in computational complexityCombinatorica, 1990
- On the method of approximationsPublished by Association for Computing Machinery (ACM) ,1989
- Lower bounds on the size of bounded depth circuits over a complete basis with logical additionMathematical Notes, 1987
- On the construction of parallel computers from various bases of boolean functionsTheoretical Computer Science, 1986