Polynomials with Rational Coefficients Which are Hard to Compute
From MaRDI portal
Publication:4778270
DOI10.1137/0203010zbMath0289.68018OpenAlexW1981241857MaRDI QIDQ4778270
Publication date: 1974
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0203010
Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Numerical computation of solutions to single equations (65H05)
Related Items
Irreducibility of multivariate polynomials, On Kolmogorov complexity in the real Turing machine setting, Why Horn formulas matter in computer science: initial structures and generic examples, Simplified lower bounds for polynomials with algebraic coefficients, Derandomization from Algebraic Hardness, Feasible arithmetic computations: Valiant's hypothesis, Fast computation of the \(N\)-th term of a \(q\)-holonomic sequence and applications, On sets of linear forms of maximal complexity, Some polynomials that are hard to compute, Lower bounds for polynomials with algebraic coefficients, On the additive complexity of polynomials, The real dimension problem is \(\text{NP}_{\mathbb R}\)-complete., Time-space tradeoffs in algebraic complexity theory, A new method to obtain lower bounds for polynomial evaluation, Unnamed Item, Complexity measures and hierarchies for the evaluation of integers and polynomials, A constructive generalization of the borel-cantelli lemma with application to the complexity of infinite strings, Evaluation of polynomials with super-preconditioning, Improved lower bounds on the number of multiplications/divisions which are necessary to evaluate polynomials, On fixed-polynomial size circuit lower bounds for uniform polynomials in the sense of Valiant, On the representation of rational functions of bounded complexity, Lower bounds in algebraic computational complexity, On commutativity and approximation, Unifying known lower bounds via geometric complexity theory, Lower bounds for some decision problems over \(C\)
