On lower bounds for read-k-times branching programs
- 1 March 1993
- journal article
- Published by Springer Nature in computational complexity
- Vol. 3 (1), 1-18
- https://doi.org/10.1007/bf01200404
Abstract
No abstract availableKeywords
This publication has 17 references indexed in Scilit:
- Lower bounds on the complexity of 1-time only branching programs (Preliminary version)Published by Springer Nature ,2006
- Superlinear Lower Bounds for Bounded-Width Branching ProgramsJournal of Computer and System Sciences, 1995
- A note on read-$k$ times branching programsRAIRO - Theoretical Informatics and Applications, 1995
- A general Sequential Time-Space Tradeoff for Finding Unique ElementsSIAM Journal on Computing, 1991
- Lower bounds to the complexity of symmetric Boolean functionsTheoretical Computer Science, 1990
- Multiparty protocols and logspace-hard pseudorandom sequencesPublished by Association for Computing Machinery (ACM) ,1989
- Nondeterministic Space is Closed under ComplementationSIAM Journal on Computing, 1988
- Generalized String MatchingSIAM Journal on Computing, 1987
- Multi-party protocolsPublished by Association for Computing Machinery (ACM) ,1983
- A Time-Space Tradeoff for Sorting on a General Sequential Model of ComputationSIAM Journal on Computing, 1982