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 circuitspolynomial identity testingmultiplications

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)

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