Time-space tradeoffs in algebraic complexity theory
From MaRDI portal
Publication:1977138
DOI10.1006/jcom.1999.0526zbMath0951.68042OpenAlexW1978035078MaRDI QIDQ1977138
M. Aldaz, Joos Heintz, Guillermo Matera, Luis Miguel Pardo, José Luis Montaña
Publication date: 2000
Published in: Journal of Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/jcom.1999.0526
Related Items
Vapnik-Chervonenkis Dimension of Parallel Arithmetic Computations, A new method to obtain lower bounds for polynomial evaluation
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On intrinsic bounds in the Nullstellensatz
- Definability and fast quantifier elimination in algebraically closed fields
- Time-space tradeoffs for matrix multiplication and the discrete Fourier transform on any general sequential random-access computer
- Bounds for the degrees in the Nullstellensatz
- Mathematical foundations of computer science 1980. Proceedings of the 9th Symposium held in Rydzyna, Poland, September 1-5, 1980
- Time-space tradeoffs for computing functions, using connectivity properties of their circuits
- Some polynomials that are hard to compute
- Application of separability and independence notions for proving lower bounds of circuit complexity
- Lower bounds for polynomials with algebraic coefficients
- A time-space tradeoff for sorting on non-oblivious machines
- Time-space tradeoffs for algebraic problems on general sequential machines
- Improved lower bounds on the number of multiplications/divisions which are necessary to evaluate polynomials
- Time-space trade-offs in a pebble game
- On the intrinsic complexity of elimination theory
- Lower bounds for diophantine approximations
- Bounds for the Hilbert function of polynomial ideals and for the degrees in the Nullstellensatz
- Simplified lower bounds for polynomials with algebraic coefficients
- Straight-line programs in geometric elimination theory
- Lower bounds for arithmetic networks
- Lower bounds for the complexity of polynomials
- On the representation of rational functions of bounded complexity
- How can a complex square root be computed in an optimal way?
- Time-Space trade-offs for some algebraic problems
- A general Sequential Time-Space Tradeoff for Finding Unique Elements
- A time-space tradeoff for language recognition
- Nullstellensatz effectif et Conjecture de Serre (Théorème de Quillen-Suslin) pour le Calcul Formel
- Space-Time Trade-Offs for Banded Matrix Problems
- A Time-Space Tradeoff for Element Distinctness
- A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation
- Computing Algebraic Formulas Using a Constant Number of Registers
- Space-time trade-offs on the FFT algorithm
- A Time-Space Trade-Off
- Sur la complexité du principe de Tarski-Seidenberg
- Sharp Effective Nullstellensatz
- Polynomials with Rational Coefficients Which are Hard to Compute
- On the Number of Nonscalar Multiplications Necessary to Evaluate Polynomials
