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 boundsmatrix inversionpermutation matricesmatrix-vector productsmatrix multiplicationbranching programinteger multiplicationconvolution of vectors
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (4)
On lower bounds for read-\(k\)-times branching programs ⋮ Time-space tradeoffs in algebraic complexity theory ⋮ Quadratic Time-Space Lower Bounds for Computing Natural Functions with a Random Oracle ⋮ Time-space tradeoffs for branching programs
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
This page was built for publication: Time-space tradeoffs for algebraic problems on general sequential machines
