Time-space tradeoffs in algebraic complexity theory
type: Item
instance of: scholarly article
title: Time-space tradeoffs in algebraic complexity theory
zbMATH Open document ID: 0951.68042
author: M. Aldaz
author: Joos Heintz
author: Guillermo Matera
author: J. L. Montaña
author: Luis Miguel Pardo
published in: Journal of Complexity
publication date: 2000-01-01T00:00:00Z
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 1444119
zbMATH Keywords: polynomial evaluation procedures
zbMATH Keywords: straight-line programs
MaRDI profile type: Publication
full work available at URL: jcom.1999.0526
OpenAlex ID: W1978035078
cites work: Time-space tradeoffs for algebraic problems on general sequential machines
cites work: Simplified lower bounds for polynomials with algebraic coefficients
cites work: A general Sequential Time-Space Tradeoff for Finding Unique Elements
cites work: Computing Algebraic Formulas Using a Constant Number of Registers
cites work: Q3770650
cites work: A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation
cites work: A Time-Space Tradeoff for Element Distinctness
cites work: A time-space tradeoff for sorting on non-oblivious machines
cites work: Q4190138
cites work: Bounds for the degrees in the Nullstellensatz
cites work: Q4331740
cites work: Q4204240
cites work: Q4203817
cites work: Q5556574
cites work: A time-space tradeoff for language recognition
cites work: Nullstellensatz effectif et Conjecture de Serre (Théorème de Quillen-Suslin) pour le Calcul Formel
cites work: Q3328651
cites work: Some polynomials that are hard to compute
cites work: Lower bounds for diophantine approximations
cites work: Straight-line programs in geometric elimination theory
cites work: Q4352797
cites work: Application of separability and independence notions for proving lower bounds of circuit complexity
cites work: Definability and fast quantifier elimination in algebraically closed fields
cites work: Q3835021
cites work: On the intrinsic complexity of elimination theory
cites work: Sur la complexité du principe de Tarski-Seidenberg
cites work: Q3942397
cites work: Lower bounds for polynomials with algebraic coefficients
cites work: Time-Space trade-offs for some algebraic problems
cites work: Sharp Effective Nullstellensatz
cites work: On intrinsic bounds in the Nullstellensatz
cites work: Q4714022
cites work: How can a complex square root be computed in an optimal way?
cites work: Q4729767
cites work: Lower bounds for arithmetic networks
cites work: Q4352783
cites work: On the Number of Nonscalar Multiplications Necessary to Evaluate Polynomials
cites work: Time-space trade-offs in a pebble game
cites work: A Time-Space Trade-Off
cites work: Mathematical foundations of computer science 1980. Proceedings of the 9th Symposium held in Rydzyna, Poland, September 1-5, 1980
cites work: Space-Time Trade-Offs for Banded Matrix Problems
cites work: Space-time trade-offs on the FFT algorithm
cites work: Q4190139
cites work: Q3920647
cites work: Improved lower bounds on the number of multiplications/divisions which are necessary to evaluate polynomials
cites work: Q4302493
cites work: Bounds for the Hilbert function of polynomial ideals and for the degrees in the Nullstellensatz
cites work: Lower bounds for the complexity of polynomials
cites work: On the representation of rational functions of bounded complexity
cites work: Polynomials with Rational Coefficients Which are Hard to Compute
cites work: Q4385517
cites work: Time-space tradeoffs for computing functions, using connectivity properties of their circuits
cites work: Q3336589
cites work: Q3259734
cites work: Time-space tradeoffs for matrix multiplication and the discrete Fourier transform on any general sequential random-access computer
DOI: 10.1006/JCOM.1999.0526
description: scientific article; zbMATH DE number 1444119