Time–Space Tradeoffs for Branching Programs
Authors:
- Paul BeamePBPaul Beame
- T.S. JayramTJT.S. Jayram
- Michael SaksMSMichael Saks
- 1 December 2001
- journal article
- Published by Elsevier in Journal of Computer and System Sciences
- Vol. 63 (4) , 542-572
Abstract
No abstract availableKeywords
This publication has 21 references indexed in Scilit:
- A simple function that requires exponential size read-once branching programsInformation Processing Letters, 1997
- Symbolic model checking for sequential circuit verificationIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1994
- On lower bounds for read-k-times branching programscomputational complexity, 1993
- The computational complexity of universal hashingTheoretical Computer Science, 1993
- Multiparty protocols, pseudorandom generators for logspace, and time-space trade-offsJournal of Computer and System Sciences, 1992
- Meanders and their applications in lower bounds argumentsJournal of Computer and System Sciences, 1988
- On the complexity of branching programs and decision trees for clique functionsJournal of the ACM, 1988
- A lower bound for read-once-only branching programsJournal of Computer and System Sciences, 1987
- Time-space trade-offs for branching programsJournal of Computer and System Sciences, 1986
- A Time-Space Tradeoff for Sorting on a General Sequential Model of ComputationSIAM Journal on Computing, 1982