Time-space tradeoffs for algebraic problems on general sequential machines
From MaRDI portal
Publication:1176102
DOI10.1016/0022-0000(91)90014-VzbMath0776.68052MaRDI QIDQ1176102
Publication date: 25 June 1992
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
lower bounds; matrix inversion; permutation matrices; matrix-vector products; matrix multiplication; branching program; integer multiplication; convolution of vectors
DB lookup for MSC labels failed
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Time-space tradeoffs for matrix multiplication and the discrete Fourier transform on any general sequential random-access computer
- Time-space trade-offs for branching programs
- Time-space tradeoffs for computing functions, using connectivity properties of their circuits
- A time-space tradeoff for sorting on non-oblivious machines
- Time-space trade-offs in a pebble game
- Time-Space trade-offs for some algebraic problems
- Bounds for Width Two Branching Programs
- Space-Time Trade-Offs for Banded Matrix Problems
- A Time-Space Tradeoff for Element Distinctness
- Generalized String Matching
- A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation
- A Time-Space Trade-Off