Computing polynomials with few multiplications

DOI10.4086/TOC.2011.V007A013MaRDI QIDQ2913800zbMATH OpenOpenAlexFDO

Authors Shachar Lovett

Publication date 27 September 2012

Published in Theory of Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4086/toc.2011.v007a013

zbMATH Keywords

arithmetic circuitsmultiplicationspolynomial identity testing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• STACS 2005
• Multiplicative complexity of polynomial multiplication over finite fields
• On parallel evaluation of certain classes of polynomials with an increasing number of variables
• Simple multivariate polynomial multiplication
• On the parallel evaluation of multivariate polynomials

Cited in

(10)

• Computing with barycentric polynomials
• Computing values of a polynomial with only few multiplications
• A simple proof for the upper bound of the computational complexity of three monomials in three variables
• A Selection of Lower Bounds for Arithmetic Circuits
• Arithmetic complexity in ring extensions
• Code Generation for Polynomial Multiplication
• Computing Elementary Symmetric Polynomials with a Subpolynomial Numberof Multiplications
• scientific article; zbMATH DE number 1929311 (Why is no real title available?)
• A super-quadratic lower bound for depth four arithmetic circuits
• On the multiplicative complexity of polynomials

This page was built for publication: Computing polynomials with few multiplications

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