On the Parallel Evaluation of Multivariate Polynomials

DOI10.1137/0208010MaRDI QIDQ4195943zbMATH OpenOpenAlexFDO

Authors 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 ComplexityEvaluation of Multivariate PolynomialsParallel Computation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cited in

(21)

• Upper bounds on the complexity of solving systems of linear equations
• Feasible arithmetic computations: Valiant's hypothesis
• Computing multivariate polynomials in parallel
• Greedy can beat pure dynamic programming
• Operator scaling: theory and applications
• Algebraic complexity classes
• Tropical complexity, Sidon sets, and dynamic programming
• Computing (and Life) Is All about Tradeoffs
• Lower bounds for monotone counting circuits
• On the depth complexity of formulas
• On the Size of Homogeneous and of Depth-Four Formulas with Low Individual Degree
• The computational power of depth five arithmetic circuits
• Lower bounds for tropical circuits and dynamic programs
• Barriers for rank methods in arithmetic complexity
• Quasipolynomial hitting sets for circuits with restricted parse trees
• Short Proofs for the Determinant Identities
• Non-commutative circuits and the sum-of-squares problem
• Shadows of Newton polytopes
• Homogeneous formulas and symmetric polynomials
• Notes on Boolean read-k and multilinear circuits
• Lower bounds on dynamic programming for maximum weight independent set

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4195943)