On the Parallel Evaluation of Multivariate Polynomials

DOI10.1137/0208010zbMath0408.68041OpenAlexW1987465321MaRDI QIDQ4195943

Laurent Hyafil

Publication date: 1979

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0208010

zbMATH Keywords

Arithmetic ComplexityParallel ComputationEvaluation of Multivariate Polynomials

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (19)

Greedy can beat pure dynamic programming ⋮ Lower bounds for monotone counting circuits ⋮ Feasible arithmetic computations: Valiant's hypothesis ⋮ Shadows of Newton polytopes ⋮ Homogeneous formulas and symmetric polynomials ⋮ Computing multivariate polynomials in parallel ⋮ Barriers for Rank Methods in Arithmetic Complexity ⋮ The Computational Power of Depth Five Arithmetic Circuits ⋮ Lower bounds for tropical circuits and dynamic programs ⋮ Unnamed Item ⋮ Non-commutative circuits and the sum-of-squares problem ⋮ On the depth complexity of formulas ⋮ On the Size of Homogeneous and of Depth-Four Formulas with Low Individual Degree ⋮ Algebraic Complexity Classes ⋮ Operator scaling: theory and applications ⋮ Tropical Complexity, Sidon Sets, and Dynamic Programming ⋮ Computing (and Life) Is All about Tradeoffs ⋮ Short Proofs for the Determinant Identities ⋮ Upper bounds on the complexity of solving systems of linear equations

This page was built for publication: On the Parallel Evaluation of Multivariate Polynomials