Time-space tradeoffs in algebraic complexity theory

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

zbMATH Keywords

straight-line programspolynomial evaluation procedures

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (3)

Vapnik-Chervonenkis Dimension of Parallel Arithmetic Computations ⋮ A new method to obtain lower bounds for polynomial evaluation ⋮ In memoriam. Succinct obituary in memoriam of Joos Heintz

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

This page was built for publication: Time-space tradeoffs in algebraic complexity theory