Test complexity of generic polynomials

DOI10.1016/0885-064X(92)90022-4zbMath0768.68034MaRDI QIDQ1201154

Peter Bürgisser, Thomas Lickteig

Publication date: 17 January 1993

Published in: Journal of Complexity (Search for Journal in Brave)

zbMATH Keywords

algebraic complexityadditive and multiplicative branching complexitieslower bounds for polynomial evaluationzerosets of polynomials

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational aspects of algebraic surfaces (14Q10) Real and complex fields (12D99)

Related Items

On the complexity of quadratic programming in real number models of computation, Semi-algebraic decision complexity, the real spectrum, and degree, Verification complexity of linear prime ideals, Distributed Algorithmic Mechanism Design and Algebraic Communication Complexity, On the parallel complexity of the polynomial ideal membership problem

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
• The complexity of partial derivatives
• A lower bound of \({1\over 2}n^2\) on linear search programs for the knapsack problem
• Proving simultaneous positivity of linear forms
• The evaluation of polynomials
• The Computational Complexity of Continued Fractions
• An Extension of Strassen’s Degree Bound
• Lower bounds for algebraic decision trees
• Simple Proofs of Lower Bounds for Polynomial Evaluation
• Additive Complexity and Zeros of Real Polynomials
• Rabin's width of a complete proof and the width of a semialgebraic set