Time space tradeoffs (getting closer to the barrier?)
- 1 January 1993
- book chapter
- Published by Springer Nature
Abstract
No abstract availableKeywords
This publication has 43 references indexed in Scilit:
- A sublinear space, polynomial time algorithm for directed s-t connectivityPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- A time-space tradeoff for Boolean matrix multiplicationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Short random walks on graphsPublished by Association for Computing Machinery (ACM) ,1993
- A general Sequential Time-Space Tradeoff for Finding Unique ElementsSIAM Journal on Computing, 1991
- Deterministic algorithms for undirected s-t connectivity using polynomial time and sublinear space.Published by Association for Computing Machinery (ACM) ,1991
- Lower bounds to the complexity of symmetric Boolean functionsTheoretical Computer Science, 1990
- Bounds on Universal SequencesSIAM Journal on Computing, 1989
- 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
- Random walks, universal traversal sequences, and the complexity of maze problemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1979