Lower bounds for deterministic and nondeterministic branching programs
- 1 January 1991
- book chapter
- Published by Springer Nature in Lecture Notes in Computer Science
Abstract
No abstract availableKeywords
This publication has 28 references indexed in Scilit:
- The Complexity of Finite FunctionsPublished by Elsevier ,1990
- Multiparty protocols and logspace-hard pseudorandom sequencesPublished by Association for Computing Machinery (ACM) ,1989
- Subquadratic simulations of circuits by branching programsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1989
- Meanders and their applications in lower bounds argumentsJournal of Computer and System Sciences, 1988
- Two lower bounds for branching programsPublished by Association for Computing Machinery (ACM) ,1986
- Bounded-width polynomial-size branching programs recognize exactly those languages in NC1Published by Association for Computing Machinery (ACM) ,1986
- Bounds for width two branching programsPublished by Association for Computing Machinery (ACM) ,1983
- An 0(n log n) sorting networkPublished by Association for Computing Machinery (ACM) ,1983
- A Time-Space Tradeoff for Sorting on a General Sequential Model of ComputationSIAM Journal on Computing, 1982
- Random walks, universal traversal sequences, and the complexity of maze problemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1979